apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A MIPT student named Misha has a birthday today, and he decided to celebrate it in his country house in suburban Moscow. n friends came by, and after a typical party they decided to play blind man's buff.

The birthday boy gets blindfolded and the other players scatter around the house. The game is played in several rounds. In each round, Misha catches exactly one of his friends and has to guess who it is. The probability of catching the i-th friend does not change between rounds and is equal to pi percent (as we know, it is directly proportional to the amount of alcohol consumed by the i-th friend) and p1 + p2 + ... + pn = 100 holds. Misha has no information about who he caught. After Misha makes an attempt to guess the caught person, the round ends. Even then, Misha isn't told whether he guessed correctly, and a new round begins.

The game ends when Misha guesses every friend at least once, that is, there exists such set of rounds k1, k2, ..., kn, that during round number ki Misha caught the i-th friend and guessed him. Misha wants to minimize the expectation of the number of rounds of the game. Despite the fact that at any point in the game Misha has no information about who he has already guessed, his friends are honest, and if they see that the condition for the end of the game is fulfilled, the game ends immediately. Find the expectation of the number of rounds in the game if Misha plays optimally.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 100) — the number of Misha's friends.

The second line contains n integers pi ($$p_i > 0, \sum_{i=1}^{n} p_i = 100$$), giving the probability to catch the i-th friend in one particular round in percent.

## Output Format
Print a single real value — the expectation of the number of rounds provided that Misha plays optimally. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

## Examples
```input
2
50 50
```
```output
5.0000000000
```
-----
```input
4
50 20 20 10
```
```output
39.2846263444
```

## Note
The optimal strategy in the first sample is to guess friends alternately.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 7.0 seconds
Memory limit: 256.0 MB

# Problem
Let's define the transformation P of a sequence of integers a1, a2, ..., an as b1, b2, ..., bn, where bi = a1 | a2 | ... | ai for all i = 1, 2, ..., n, where | is the bitwise OR operation.

Vasya consequently applies the transformation P to all sequences of length n consisting of integers from 1 to 2k - 1 inclusive. He wants to know how many of these sequences have such property that their transformation is a strictly increasing sequence. Help him to calculate this number modulo 109 + 7.

## Input Format
The only line of the input contains two integers n and k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 30 000).

## Output Format
Print a single integer — the answer to the problem modulo 109 + 7.

## Examples
```input
1 2
```
```output
3
```
-----
```input
2 3
```
```output
30
```
-----
```input
3 3
```
```output
48
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Door's family is going celebrate Famil Doors's birthday party. They love Famil Door so they are planning to make his birthday cake weird!

The cake is a n × n square consisting of equal squares with side length 1. Each square is either empty or consists of a single chocolate. They bought the cake and randomly started to put the chocolates on the cake. The value of Famil Door's happiness will be equal to the number of pairs of cells with chocolates that are in the same row or in the same column of the cake. Famil Doors's family is wondering what is the amount of happiness of Famil going to be?

Please, note that any pair can be counted no more than once, as two different cells can't share both the same row and the same column.

## Input Format
In the first line of the input, you are given a single integer n (1 ≤ n ≤ 100) — the length of the side of the cake.

Then follow n lines, each containing n characters. Empty cells are denoted with '.', while cells that contain chocolates are denoted by 'C'.

## Output Format
Print the value of Famil Door's happiness, i.e. the number of pairs of chocolate pieces that share the same row or the same column.

## Examples
```input
3
.CC
C..
C.C
```
```output
4
```
-----
```input
4
CC..
C..C
.CC.
.CC.
```
```output
9
```

## Note
If we number rows from top to bottom and columns from left to right, then, pieces that share the same row in the first sample are:

1. (1, 2) and (1, 3)
2. (3, 1) and (3, 3)

1. (2, 1) and (3, 1)
2. (1, 3) and (3, 3)

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Famil Door wants to celebrate his birthday with his friends from Far Far Away. He has n friends and each of them can come to the party in a specific range of days of the year from ai to bi. Of course, Famil Door wants to have as many friends celebrating together with him as possible.

Far cars are as weird as Far Far Away citizens, so they can only carry two people of opposite gender, that is exactly one male and one female. However, Far is so far from here that no other transportation may be used to get to the party.

Famil Door should select some day of the year and invite some of his friends, such that they all are available at this moment and the number of male friends invited is equal to the number of female friends invited. Find the maximum number of friends that may present at the party.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — then number of Famil Door's friends.

Then follow n lines, that describe the friends. Each line starts with a capital letter 'F' for female friends and with a capital letter 'M' for male friends. Then follow two integers ai and bi (1 ≤ ai ≤ bi ≤ 366), providing that the i-th friend can come to the party from day ai to day bi inclusive.

## Output Format
Print the maximum number of people that may come to Famil Door's party.

## Examples
```input
4
M 151 307
F 343 352
F 117 145
M 24 128
```
```output
2
```
-----
```input
6
M 128 130
F 128 131
F 131 140
F 131 141
M 131 200
M 140 200
```
```output
4
```

## Note
In the first sample, friends 3 and 4 can come on any day in range [117, 128].

In the second sample, friends with indices 3, 4, 5 and 6 can come on day 140.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
As you know, every birthday party has a cake! This time, Babaei is going to prepare the very special birthday party's cake.

Simple cake is a cylinder of some radius and height. The volume of the simple cake is equal to the volume of corresponding cylinder. Babaei has n simple cakes and he is going to make a special cake placing some cylinders on each other.

However, there are some additional culinary restrictions. The cakes are numbered in such a way that the cake number i can be placed only on the table or on some cake number j where j < i. Moreover, in order to impress friends Babaei will put the cake i on top of the cake j only if the volume of the cake i is strictly greater than the volume of the cake j.

Babaei wants to prepare a birthday cake that has a maximum possible total volume. Help him find this value.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of simple cakes Babaei has.

Each of the following n lines contains two integers ri and hi (1 ≤ ri, hi ≤ 10 000), giving the radius and height of the i-th cake.

## Output Format
Print the maximum volume of the cake that Babaei can make. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

## Examples
```input
2
100 30
40 10
```
```output
942477.796077000
```
-----
```input
4
1 1
9 7
1 4
10 7
```
```output
3983.539484752
```

## Note
In first sample, the optimal way is to choose the cake number 1.

In second sample, the way to get the maximum volume is to use cakes with indices 1, 2 and 4.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
In Berland recently a new collection of toys went on sale. This collection consists of 109 types of toys, numbered with integers from 1 to 109. A toy from the new collection of the i-th type costs i bourles.

Tania has managed to collect n different types of toys a1, a2, ..., an from the new collection. Today is Tanya's birthday, and her mother decided to spend no more than m bourles on the gift to the daughter. Tanya will choose several different types of toys from the new collection as a gift. Of course, she does not want to get a type of toy which she already has.

Tanya wants to have as many distinct types of toys in her collection as possible as the result. The new collection is too diverse, and Tanya is too little, so she asks you to help her in this.

## Input Format
The first line contains two integers n (1 ≤ n ≤ 100 000) and m (1 ≤ m ≤ 109) — the number of types of toys that Tanya already has and the number of bourles that her mom is willing to spend on buying new toys.

The next line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the types of toys that Tanya already has.

## Output Format
In the first line print a single integer k — the number of different types of toys that Tanya should choose so that the number of different types of toys in her collection is maximum possible. Of course, the total cost of the selected toys should not exceed m.

In the second line print k distinct space-separated integers t1, t2, ..., tk (1 ≤ ti ≤ 109) — the types of toys that Tanya should choose.

If there are multiple answers, you may print any of them. Values of ti can be printed in any order.

## Examples
```input
3 7
1 3 4
```
```output
2
2 5
```
-----
```input
4 14
4 6 12 8
```
```output
4
7 2 3 1
```

## Note
In the first sample mom should buy two toys: one toy of the 2-nd type and one toy of the 5-th type. At any other purchase for 7 bourles (assuming that the toys of types 1, 3 and 4 have already been bought), it is impossible to buy two and more toys.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Long ago, Vasily built a good fence at his country house. Vasily calls a fence good, if it is a series of n consecutively fastened vertical boards of centimeter width, the height of each in centimeters is a positive integer. The house owner remembers that the height of the i-th board to the left is hi.

Today Vasily decided to change the design of the fence he had built, by cutting his top connected part so that the fence remained good. The cut part should consist of only the upper parts of the boards, while the adjacent parts must be interconnected (share a non-zero length before cutting out of the fence).

You, as Vasily's curious neighbor, will count the number of possible ways to cut exactly one part as is described above. Two ways to cut a part are called distinct, if for the remaining fences there is such i, that the height of the i-th boards vary.

As Vasily's fence can be very high and long, get the remainder after dividing the required number of ways by 1 000 000 007 (109 + 7).

## Input Format
The first line contains integer n (1 ≤ n ≤ 1 000 000) — the number of boards in Vasily's fence.

The second line contains n space-separated numbers h1, h2, ..., hn (1 ≤ hi ≤ 109), where hi equals the height of the i-th board to the left.

## Output Format
Print the remainder after dividing r by 1 000 000 007, where r is the number of ways to cut exactly one connected part so that the part consisted of the upper parts of the boards and the remaining fence was good.

## Examples
```input
2
1 1
```
```output
0
```
-----
```input
3
3 4 2
```
```output
13
```

## Note
From the fence from the first example it is impossible to cut exactly one piece so as the remaining fence was good.

All the possible variants of the resulting fence from the second sample look as follows (the grey shows the cut out part):

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
As you know, the game of "Nim" is played with n piles of stones, where the i-th pile initially contains ai stones. Two players alternate the turns. During a turn a player picks any non-empty pile and removes any positive number of stones from it. The one who is not able to make a move loses the game.

Petya and Vasya are tired of playing Nim, so they invented their own version of the game and named it the "Gambling Nim". They have n two-sided cards, one side of the i-th card has number ai written on it, while the other side has number bi. At the beginning of the game the players put all the cards on the table, each card only one of its sides up, and this side is chosen independently and uniformly. Thus they obtain a sequence c1, c2, ..., cn, where ci is equal to ai or bi. Then they take n piles of stones, with i-th pile containing exactly ci stones and play Nim. Petya takes the first turn.

Given that both players play optimally, find the probability of Petya's victory. Output the answer as an irreducible fraction.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of cards in the deck.

Each of the following n lines contains the description of one card, consisting of two integers ai and bi (0 ≤ ai, bi ≤ 1018).

## Output Format
Output the answer as an irreducible fraction p / q. If the probability of Petya's victory is 0, print 0/1.

## Examples
```input
2
1 1
1 1
```
```output
0/1
```
-----
```input
2
1 2
1 2
```
```output
1/2
```
-----
```input
3
0 4
1 5
2 3
```
```output
1/1
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Ted has a pineapple. This pineapple is able to bark like a bulldog! At time t (in seconds) it barks for the first time. Then every s seconds after it, it barks twice with 1 second interval. Thus it barks at times t, t + s, t + s + 1, t + 2s, t + 2s + 1, etc.

Barney woke up in the morning and wants to eat the pineapple, but he can't eat it when it's barking. Barney plans to eat it at time x (in seconds), so he asked you to tell him if it's gonna bark at that time.

## Input Format
The first and only line of input contains three integers t, s and x (0 ≤ t, x ≤ 109, 2 ≤ s ≤ 109) — the time the pineapple barks for the first time, the pineapple barking interval, and the time Barney wants to eat the pineapple respectively.

## Output Format
Print a single "YES" (without quotes) if the pineapple will bark at time x or a single "NO" (without quotes) otherwise in the only line of output.

## Examples
```input
3 10 4
```
```output
NO
```
-----
```input
3 10 3
```
```output
YES
```
-----
```input
3 8 51
```
```output
YES
```
-----
```input
3 8 52
```
```output
YES
```

## Note
In the first and the second sample cases pineapple will bark at moments 3, 13, 14, ..., so it won't bark at the moment 4 and will bark at the moment 3.

In the third and fourth sample cases pineapple will bark at moments 3, 11, 12, 19, 20, 27, 28, 35, 36, 43, 44, 51, 52, 59, ..., so it will bark at both moments 51 and 52.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Barney is standing in a bar and starring at a pretty girl. He wants to shoot her with his heart arrow but he needs to know the distance between him and the girl to make his shot accurate.

Barney asked the bar tender Carl about this distance value, but Carl was so busy talking to the customers so he wrote the distance value (it's a real number) on a napkin. The problem is that he wrote it in scientific notation. The scientific notation of some real number x is the notation of form AeB, where A is a real number and B is an integer and x = A × 10B is true. In our case A is between 0 and 9 and B is non-negative.

Barney doesn't know anything about scientific notation (as well as anything scientific at all). So he asked you to tell him the distance value in usual decimal representation with minimal number of digits after the decimal point (and no decimal point if it is an integer). See the output format for better understanding.

## Input Format
The first and only line of input contains a single string of form a.deb where a, d and b are integers and e is usual character 'e' (0 ≤ a ≤ 9, 0 ≤ d < 10100, 0 ≤ b ≤ 100) — the scientific notation of the desired distance value.

a and b contain no leading zeros and d contains no trailing zeros (but may be equal to 0). Also, b can not be non-zero if a is zero.

## Output Format
Print the only real number x (the desired distance value) in the only line in its decimal notation.

Thus if x is an integer, print it's integer value without decimal part and decimal point and without leading zeroes.

Otherwise print x in a form of p.q such that p is an integer that have no leading zeroes (but may be equal to zero), and q is an integer that have no trailing zeroes (and may not be equal to zero).

## Examples
```input
8.549e2
```
```output
854.9
```
-----
```input
8.549e3
```
```output
8549
```
-----
```input
0.33e0
```
```output
0.33
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given array consisting of n integers. Your task is to find the maximum length of an increasing subarray of the given array.

A subarray is the sequence of consecutive elements of the array. Subarray is called increasing if each element of this subarray strictly greater than previous.

## Input Format
The first line contains single positive integer n (1 ≤ n ≤ 105) — the number of integers.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

## Output Format
Print the maximum length of an increasing subarray of the given array.

## Examples
```input
5
1 7 2 11 15
```
```output
3
```
-----
```input
6
100 100 100 100 100 100
```
```output
1
```
-----
```input
3
1 2 3
```
```output
3
```

Now solve the problem and return the code.