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
Dima and his friends have been playing hide and seek at Dima's place all night. As a result, Dima's place got messy. In the morning they decided that they need to clean the place.

To decide who exactly would clean the apartment, the friends want to play a counting-out game. First, all the guys stand in a circle, and then each of them shows some number of fingers on one hand (one to five), and then the boys count in a circle, starting from Dima, the number of people, respective to the total number of fingers shown. The person on who the countdown stops will clean the apartment.

For example, if Dima and one of his friends played hide and seek, and 7 fingers were shown during the counting-out, then Dima would clean the place. If there were 2 or say, 8 fingers shown, then his friend would clean the place.

Dima knows how many fingers each of his friends will show during the counting-out. Now he is interested in the number of ways to show some number of fingers on one hand (one to five), so that he did not have to clean the place. Help Dima.

## Input Format
The first line contains integer n (1 ≤ n ≤ 100) — the number of Dima's friends. Dima himself isn't considered to be his own friend. The second line contains n positive integers, not exceeding 5, representing, how many fingers the Dima's friends will show.

The numbers in the lines are separated by a single space.

## Output Format
In a single line print the answer to the problem.

## Examples
```input
1
1
```
```output
3
```
-----
```input
1
2
```
```output
2
```
-----
```input
2
3 5
```
```output
3
```

## Note
In the first sample Dima can show 1, 3 or 5 fingers. If Dima shows 3 fingers, then the counting-out will go like that: Dima, his friend, Dima, his friend.

In the second sample Dima can show 2 or 4 fingers.

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
Dima got into number sequences. Now he's got sequence a1, a2, ..., an, consisting of n positive integers. Also, Dima has got a function f(x), which can be defined with the following recurrence:

- f(0) = 0;
- f(2·x) = f(x);
- f(2·x + 1) = f(x) + 1.

Dima wonders, how many pairs of indexes (i, j) (1 ≤ i < j ≤ n) are there, such that f(ai) = f(aj). Help him, count the number of such pairs.

## Input Format
The first line contains integer n (1 ≤ n ≤ 105). The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

The numbers in the lines are separated by single spaces.

## Output Format
In a single line print the answer to the problem.

Please, don't use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

## Note
In the first sample any pair (i, j) will do, so the answer is 3.

In the second sample only pair (1, 2) will do.

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
The Little Girl loves problems on games very much. Here's one of them.

Two players have got a string s, consisting of lowercase English letters. They play a game that is described by the following rules:

- The players move in turns; In one move the player can remove an arbitrary letter from string s.
- If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins. A palindrome is a string that reads the same both ways (from left to right, and vice versa). For example, string "abba" is a palindrome and string "abc" isn't.

Determine which player will win, provided that both sides play optimally well — the one who moves first or the one who moves second.

## Input Format
The input contains a single line, containing string s (1 ≤ |s|  ≤  103). String s consists of lowercase English letters.

## Output Format
In a single line print word "First" if the first player wins (provided that both players play optimally well). Otherwise, print word "Second". Print the words without the quotes.

## Examples
```input
aba
```
```output
First
```
-----
```input
abca
```
```output
Second
```

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
A little girl loves problems on bitwise operations very much. Here's one of them.

You are given two integers l and r. Let's consider the values of $$a \oplus b$$ for all pairs of integers a and b (l ≤ a ≤ b ≤ r). Your task is to find the maximum value among all considered ones.

Expression $$x \oplus y$$ means applying bitwise excluding or operation to integers x and y. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is represented as "^", in Pascal — as "xor".

## Input Format
The single line contains space-separated integers l and r (1 ≤ l ≤ r ≤ 1018).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

## Output Format
In a single line print a single integer — the maximum value of $$a \oplus b$$ for all pairs of integers a, b (l ≤ a ≤ b ≤ r).

## Examples
```input
1 2
```
```output
3
```
-----
```input
8 16
```
```output
31
```
-----
```input
1 1
```
```output
0
```

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
Bessie and the cows have recently been playing with "cool" sequences and are trying to construct some. Unfortunately they are bad at arithmetic, so they need your help!

A pair (x, y) of positive integers is "cool" if x can be expressed as the sum of y consecutive integers (not necessarily positive). A sequence (a1, a2, ..., an) is "cool" if the pairs (a1, a2), (a2, a3), ..., (an - 1, an) are all cool.

The cows have a sequence of n positive integers, a1, a2, ..., an. In one move, they may replace some ai with any other positive integer (there are no other limits on the new value of ai). Determine the smallest number of moves needed to make the resulting sequence cool.

## Input Format
The first line contains a single integer, n (2 ≤ n ≤ 5000). The next line contains n space-separated integers, a1, a2, ..., an (1 ≤ ai ≤ 1015).

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

## Output Format
A single integer, the minimum number of ai that must be changed to make the sequence cool.

## Examples
```input
3
6 4 1
```
```output
0
```
-----
```input
4
20 6 3 4
```
```output
2
```

## Note
In the first sample, the sequence is already cool, so we don't need to change any elements. In the second sample, we can change a2 to 5 and a3 to 10 to make (20, 5, 10, 4) which is cool. This changes 2 elements.

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
One day, liouzhou_101 got a chat record of Freda and Rainbow. Out of curiosity, he wanted to know which sentences were said by Freda, and which were said by Rainbow. According to his experience, he thought that Freda always said "lala." at the end of her sentences, while Rainbow always said "miao." at the beginning of his sentences. For each sentence in the chat record, help liouzhou_101 find whose sentence it is.

## Input Format
The first line of the input contains an integer n (1 ≤ n ≤ 10), number of sentences in the chat record. Each of the next n lines contains a sentence. A sentence is a string that contains only Latin letters (A-Z, a-z), underline (_), comma (,), point (.) and space ( ). Its length doesn’t exceed 100.

## Output Format
For each sentence, output "Freda's" if the sentence was said by Freda, "Rainbow's" if the sentence was said by Rainbow, or "OMG>.< I don't know!" if liouzhou_101 can’t recognize whose sentence it is. He can’t recognize a sentence if it begins with "miao." and ends with "lala.", or satisfies neither of the conditions.

## Examples
```input
5
I will go to play with you lala.
wow, welcome.
miao.lala.
miao.
miao .
```
```output
Freda's
OMG>.< I don't know!
OMG>.< I don't know!
Rainbow's
OMG>.< I don't know!
```

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
SmallR is an archer. SmallR is taking a match of archer with Zanoes. They try to shoot in the target in turns, and SmallR shoots first. The probability of shooting the target each time is $${ \frac { a } { b } }$$ for SmallR while $$\frac{c}{d}$$ for Zanoes. The one who shoots in the target first should be the winner.

Output the probability that SmallR will win the match.

## Input Format
A single line contains four integers $$a,b,c,d \ (1 \leq a,b,c,d \leq 1000, 0 < \frac{a}{b} < 1, 0 < \frac{c}{d} < 1)$$.

## Output Format
Print a single real number, the probability that SmallR will win the match.

The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

## Examples
```input
1 2 1 2
```
```output
0.666666666667
```

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: 0.5 seconds
Memory limit: 256.0 MB

# Problem
You are given a cube of size k × k × k, which consists of unit cubes. Two unit cubes are considered neighbouring, if they have common face.

Your task is to paint each of k3 unit cubes one of two colours (black or white), so that the following conditions must be satisfied:

- each white cube has exactly 2 neighbouring cubes of white color;
- each black cube has exactly 2 neighbouring cubes of black color.

## Input Format
The first line contains integer k (1 ≤ k ≤ 100), which is size of the cube.

## Output Format
Print -1 if there is no solution. Otherwise, print the required painting of the cube consequently by layers. Print a k × k matrix in the first k lines, showing how the first layer of the cube should be painted. In the following k lines print a k × k matrix — the way the second layer should be painted. And so on to the last k-th layer. Note that orientation of the cube in the space does not matter.

Mark a white unit cube with symbol "w" and a black one with "b". Use the format of output data, given in the test samples. You may print extra empty lines, they will be ignored.

## Examples
```input
1
```
```output
-1
```
-----
```input
2
```
```output
bb
ww
bb
ww
```

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
Iahub got bored, so he invented a game to be played on paper.

He writes n integers a1, a2, ..., an. Each of those integers can be either 0 or 1. He's allowed to do exactly one move: he chooses two indices i and j (1 ≤ i ≤ j ≤ n) and flips all values ak for which their positions are in range [i, j] (that is i ≤ k ≤ j). Flip the value of x means to apply operation x = 1 - x.

The goal of the game is that after exactly one move to obtain the maximum number of ones. Write a program to solve the little game of Iahub.

## Input Format
The first line of the input contains an integer n (1 ≤ n ≤ 100). In the second line of the input there are n integers: a1, a2, ..., an. It is guaranteed that each of those n values is either 0 or 1.

## Output Format
Print an integer — the maximal number of 1s that can be obtained after exactly one move.

## Examples
```input
5
1 0 0 1 0
```
```output
4
```
-----
```input
4
1 0 0 1
```
```output
4
```

## Note
In the first case, flip the segment from 2 to 5 (i = 2, j = 5). That flip changes the sequence, it becomes: [1 1 1 0 1]. So, it contains four ones. There is no way to make the whole sequence equal to [1 1 1 1 1].

In the second case, flipping only the second and the third element (i = 2, j = 3) will turn all numbers into 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
There is a long plate s containing n digits. Iahub wants to delete some digits (possibly none, but he is not allowed to delete all the digits) to form his "magic number" on the plate, a number that is divisible by 5. Note that, the resulting number may contain leading zeros.

Now Iahub wants to count the number of ways he can obtain magic number, modulo 1000000007 (109 + 7). Two ways are different, if the set of deleted positions in s differs.

Look at the input part of the statement, s is given in a special form.

## Input Format
In the first line you're given a string a (1 ≤ |a| ≤ 105), containing digits only. In the second line you're given an integer k (1 ≤ k ≤ 109). The plate s is formed by concatenating k copies of a together. That is n = |a|·k.

## Output Format
Print a single integer — the required number of ways modulo 1000000007 (109 + 7).

## Examples
```input
1256
1
```
```output
4
```
-----
```input
13990
2
```
```output
528
```
-----
```input
555
2
```
```output
63
```

## Note
In the first case, there are four possible ways to make a number that is divisible by 5: 5, 15, 25 and 125.

In the second case, remember to concatenate the copies of a. The actual plate is 1399013990.

In the third case, except deleting all digits, any choice will do. Therefore there are 26 - 1 = 63 possible ways to delete digits.

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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Iahub wants to meet his girlfriend Iahubina. They both live in Ox axis (the horizontal axis). Iahub lives at point 0 and Iahubina at point d.

Iahub has n positive integers a1, a2, ..., an. The sum of those numbers is d. Suppose p1, p2, ..., pn is a permutation of {1, 2, ..., n}. Then, let b1 = ap1, b2 = ap2 and so on. The array b is called a "route". There are n! different routes, one for each permutation p.

Iahub's travel schedule is: he walks b1 steps on Ox axis, then he makes a break in point b1. Then, he walks b2 more steps on Ox axis and makes a break in point b1 + b2. Similarly, at j-th (1 ≤ j ≤ n) time he walks bj more steps on Ox axis and makes a break in point b1 + b2 + ... + bj.

Iahub is very superstitious and has k integers which give him bad luck. He calls a route "good" if he never makes a break in a point corresponding to one of those k numbers. For his own curiosity, answer how many good routes he can make, modulo 1000000007 (109 + 7).

## Input Format
The first line contains an integer n (1 ≤ n ≤ 24). The following line contains n integers: a1, a2, ..., an (1 ≤ ai ≤ 109).

The third line contains integer k (0 ≤ k ≤ 2). The fourth line contains k positive integers, representing the numbers that give Iahub bad luck. Each of these numbers does not exceed 109.

## Output Format
Output a single integer — the answer of Iahub's dilemma modulo 1000000007 (109 + 7).

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

## Note
In the first case consider six possible orderings:

- [2, 3, 5]. Iahub will stop at position 2, 5 and 10. Among them, 5 is bad luck for him.
- [2, 5, 3]. Iahub will stop at position 2, 7 and 10. Among them, 7 is bad luck for him.
- [3, 2, 5]. He will stop at the unlucky 5.
- [3, 5, 2]. This is a valid ordering.
- [5, 2, 3]. He got unlucky twice (5 and 7).
- [5, 3, 2]. Iahub would reject, as it sends him to position 5.

In the second case, note that it is possible that two different ways have the identical set of stopping. In fact, all six possible ways have the same stops: [2, 4, 6], so there's no bad luck for Iahub.

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
Simon has a rectangular table consisting of n rows and m columns. Simon numbered the rows of the table from top to bottom starting from one and the columns — from left to right starting from one. We'll represent the cell on the x-th row and the y-th column as a pair of numbers (x, y). The table corners are cells: (1, 1), (n, 1), (1, m), (n, m).

Simon thinks that some cells in this table are good. Besides, it's known that no good cell is the corner of the table.

Initially, all cells of the table are colorless. Simon wants to color all cells of his table. In one move, he can choose any good cell of table (x1, y1), an arbitrary corner of the table (x2, y2) and color all cells of the table (p, q), which meet both inequations: min(x1, x2) ≤ p ≤ max(x1, x2), min(y1, y2) ≤ q ≤ max(y1, y2).

Help Simon! Find the minimum number of operations needed to color all cells of the table. Note that you can color one cell multiple times.

## Input Format
The first line contains exactly two integers n, m (3 ≤ n, m ≤ 50).

Next n lines contain the description of the table cells. Specifically, the i-th line contains m space-separated integers ai1, ai2, ..., aim. If aij equals zero, then cell (i, j) isn't good. Otherwise aij equals one. It is guaranteed that at least one cell is good. It is guaranteed that no good cell is a corner.

## Output Format
Print a single number — the minimum number of operations Simon needs to carry out his idea.

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

## Note
In the first sample, the sequence of operations can be like this:

- For the first time you need to choose cell (2, 2) and corner (1, 1).
- For the second time you need to choose cell (2, 2) and corner (3, 3).
- For the third time you need to choose cell (2, 2) and corner (3, 1).
- For the fourth time you need to choose cell (2, 2) and corner (1, 3).

In the second sample the sequence of operations can be like this:

- For the first time you need to choose cell (3, 1) and corner (4, 3).
- For the second time you need to choose cell (2, 3) and corner (1, 1).

Now solve the problem and return the code.