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

# Problem
You are given a text of single-space separated words, consisting of small and capital Latin letters.

Volume of the word is number of capital letters in the word. Volume of the text is maximum volume of all words in the text.

Calculate the volume of the given text.

## Input Format
The first line contains one integer number n (1 ≤ n ≤ 200) — length of the text.

The second line contains text of single-space separated words s1, s2, ..., si, consisting only of small and capital Latin letters.

## Output Format
Print one integer number — volume of text.

## Examples
```input
7
NonZERO
```
```output
5
```
-----
```input
24
this is zero answer text
```
```output
0
```
-----
```input
24
Harbour Space University
```
```output
1
```

## Note
In the first example there is only one word, there are 5 capital letters in it.

In the second example all of the words contain 0 capital letters.

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
The flag of Berland is such rectangular field n × m that satisfies following conditions:

- Flag consists of three colors which correspond to letters 'R', 'G' and 'B'.
- Flag consists of three equal in width and height stripes, parralel to each other and to sides of the flag. Each stripe has exactly one color.
- Each color should be used in exactly one stripe.

You are given a field n × m, consisting of characters 'R', 'G' and 'B'. Output "YES" (without quotes) if this field corresponds to correct flag of Berland. Otherwise, print "NO" (without quotes).

## Input Format
The first line contains two integer numbers n and m (1 ≤ n, m ≤ 100) — the sizes of the field.

Each of the following n lines consisting of m characters 'R', 'G' and 'B' — the description of the field.

## Output Format
Print "YES" (without quotes) if the given field corresponds to correct flag of Berland . Otherwise, print "NO" (without quotes).

## Examples
```input
6 5
RRRRR
RRRRR
BBBBB
BBBBB
GGGGG
GGGGG
```
```output
YES
```
-----
```input
4 3
BRG
BRG
BRG
BRG
```
```output
YES
```
-----
```input
6 7
RRRGGGG
RRRGGGG
RRRGGGG
RRRBBBB
RRRBBBB
RRRBBBB
```
```output
NO
```
-----
```input
4 4
RRRR
RRRR
BBBB
GGGG
```
```output
NO
```

## Note
The field in the third example doesn't have three parralel stripes.

Rows of the field in the fourth example are parralel to each other and to borders. But they have different heights — 2, 1 and 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's call the roundness of the number the number of zeros to which it ends.

You have an array of n numbers. You need to choose a subset of exactly k numbers so that the roundness of the product of the selected numbers will be maximum possible.

## Input Format
The first line contains two integer numbers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ n).

The second line contains n space-separated integer numbers a1, a2, ..., an (1 ≤ ai ≤ 1018).

## Output Format
Print maximal roundness of product of the chosen subset of length k.

## Examples
```input
3 2
50 4 20
```
```output
3
```
-----
```input
5 3
15 16 3 25 9
```
```output
3
```
-----
```input
3 3
9 77 13
```
```output
0
```

## Note
In the first example there are 3 subsets of 2 numbers. [50, 4] has product 200 with roundness 2, [4, 20] — product 80, roundness 1, [50, 20] — product 1000, roundness 3.

In the second example subset [15, 16, 25] has product 6000, roundness 3.

In the third example all subsets has product with roundness 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya is studying number theory. He has denoted a function f(a, b) such that:

- f(a, 0) = 0;
- f(a, b) = 1 + f(a, b - gcd(a, b)), where gcd(a, b) is the greatest common divisor of a and b.

Vasya has two numbers x and y, and he wants to calculate f(x, y). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.

## Input Format
The first line contains two integer numbers x and y (1 ≤ x, y ≤ 1012).

## Output Format
Print f(x, y).

## Examples
```input
3 5
```
```output
3
```
-----
```input
6 3
```
```output
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
Consider the function p(x), where x is an array of m integers, which returns an array y consisting of m + 1 integers such that yi is equal to the sum of first i elements of array x (0 ≤ i ≤ m).

You have an infinite sequence of arrays A0, A1, A2..., where A0 is given in the input, and for each i ≥ 1 Ai = p(Ai - 1). Also you have a positive integer k. You have to find minimum possible i such that Ai contains a number which is larger or equal than k.

## Input Format
The first line contains two integers n and k (2 ≤ n ≤ 200000, 1 ≤ k ≤ 1018). n is the size of array A0.

The second line contains n integers A00, A01... A0n - 1 — the elements of A0 (0 ≤ A0i ≤ 109). At least two elements of A0 are positive.

## Output Format
Print the minimum i such that Ai contains a number which is larger or equal than k.

## Examples
```input
2 2
1 1
```
```output
1
```
-----
```input
3 6
1 1 1
```
```output
2
```
-----
```input
3 1
1 0 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: 512.0 MB

# Problem
Ivan is reading a book about tournaments. He knows that a tournament is an oriented graph with exactly one oriented edge between each pair of vertices. The score of a vertex is the number of edges going outside this vertex.

Yesterday Ivan learned Landau's criterion: there is tournament with scores d1 ≤ d2 ≤ ... ≤ dn if and only if $$d_1 + \cdots + d_k \geqslant \frac{k(k-1)}{2}$$ for all 1 ≤ k < n and $$d_{1}+d_{2}+\cdots+d_{n}=\frac{n(n-1)}{2}$$.

Now, Ivan wanna solve following problem: given a set of numbers S = {a1, a2, ..., am}, is there a tournament with given set of scores? I.e. is there tournament with sequence of scores d1, d2, ..., dn such that if we remove duplicates in scores, we obtain the required set {a1, a2, ..., am}?

Find a tournament with minimum possible number of vertices.

## Input Format
The first line contains a single integer m (1 ≤ m ≤ 31).

The next line contains m distinct integers a1, a2, ..., am (0 ≤ ai ≤ 30) — elements of the set S. It is guaranteed that all elements of the set are distinct.

## Output Format
If there are no such tournaments, print string "=(" (without quotes).

Otherwise, print an integer n — the number of vertices in the tournament.

Then print n lines with n characters — matrix of the tournament. The j-th element in the i-th row should be 1 if the edge between the i-th and the j-th vertices is oriented towards the j-th vertex, and 0 otherwise. The main diagonal should contain only zeros.

## Examples
```input
2
1 2
```
```output
4
0011
1001
0100
0010
```
-----
```input
2
0 3
```
```output
6
000111
100011
110001
011001
001101
000000
```

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: 1024.0 MB

# Problem
The presidential election is coming in Bearland next year! Everybody is so excited about this!

So far, there are three candidates, Alice, Bob, and Charlie.

There are n citizens in Bearland. The election result will determine the life of all citizens of Bearland for many years. Because of this great responsibility, each of n citizens will choose one of six orders of preference between Alice, Bob and Charlie uniformly at random, independently from other voters.

The government of Bearland has devised a function to help determine the outcome of the election given the voters preferences. More specifically, the function is $$f(x_{1},x_{2},\ldots,x_{n}):\{0,1\}^{n}\to\{0,1\}$$ (takes n boolean numbers and returns a boolean number). The function also obeys the following property: f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn).

Three rounds will be run between each pair of candidates: Alice and Bob, Bob and Charlie, Charlie and Alice. In each round, xi will be equal to 1, if i-th citizen prefers the first candidate to second in this round, and 0 otherwise. After this, y = f(x1, x2, ..., xn) will be calculated. If y = 1, the first candidate will be declared as winner in this round. If y = 0, the second will be the winner, respectively.

Define the probability that there is a candidate who won two rounds as p. p·6n is always an integer. Print the value of this integer modulo 109 + 7 = 1 000 000 007.

## Input Format
The first line contains one integer n (1 ≤ n ≤ 20).

The next line contains a string of length 2n of zeros and ones, representing function f. Let bk(x) the k-th bit in binary representation of x, i-th (0-based) digit of this string shows the return value of f(b1(i), b2(i), ..., bn(i)).

It is guaranteed that f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn) for any values of x1, x2, ldots, xn.

## Output Format
Output one integer — answer to the problem.

## Examples
```input
3
01010101
```
```output
216
```
-----
```input
3
01101001
```
```output
168
```

## Note
In first sample, result is always fully determined by the first voter. In other words, f(x1, x2, x3) = x1. Thus, any no matter what happens, there will be a candidate who won two rounds (more specifically, the candidate who is at the top of voter 1's preference list), so p = 1, and we print 1·63 = 216.

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
You have a bag of balls of n different colors. You have ai balls of the i-th color.

While there are at least two different colored balls in the bag, perform the following steps:

- Take out two random balls without replacement one by one. These balls might be the same color.
- Color the second ball to the color of the first ball. You are not allowed to switch the order of the balls in this step.
- Place both balls back in the bag.
- All these actions take exactly one second.

Let M = 109 + 7. It can be proven that the expected amount of time needed before you stop can be represented as a rational number $$\frac{p}{q}$$, where P and Q are coprime integers and where Q is not divisible by M. Return the value $$P \cdot Q^{-1} \mod M$$.

## Input Format
The first line of input will contain a single integer n (1 ≤ n ≤ 2 500) — the number of colors.

The next line of input will contain n space separated integers a1, a2, ..., an (1 ≤ ai ≤ 105) — the number of balls of each color.

## Output Format
Print a single integer, the answer to the problem.

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

## Note
In the first sample, no matter what happens, the balls will become the same color after one step.

For the second sample, we have 6 balls. Let’s label the balls from 1 to 6, and without loss of generality, let’s say balls 1,2,3 are initially color 1, balls 4,5 are color 2, and ball 6 are color 3.

Here is an example of how these steps can go:

- We choose ball 5 and ball 6. Ball 6 then becomes color 2.
- We choose ball 4 and ball 5. Ball 5 remains the same color (color 2).
- We choose ball 1 and ball 5. Ball 5 becomes color 1.
- We choose ball 6 and ball 5. Ball 5 becomes color 2.
- We choose ball 3 and ball 4. Ball 4 becomes color 1.
- We choose ball 4 and ball 6. Ball 6 becomes color 1.
- We choose ball 2 and ball 5. Ball 5 becomes color 1.

It can be shown that the answer to this case is $${ \frac { 8 3 } { 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Harry Potter is on a mission to destroy You-Know-Who's Horcruxes. The first Horcrux that he encountered in the Chamber of Secrets is Tom Riddle's diary. The diary was with Ginny and it forced her to open the Chamber of Secrets. Harry wants to know the different people who had ever possessed the diary to make sure they are not under its influence.

He has names of n people who possessed the diary in order. You need to tell, for each person, if he/she possessed the diary at some point before or not.

Formally, for a name si in the i-th line, output "YES" (without quotes) if there exists an index j such that si = sj and j < i, otherwise, output "NO" (without quotes).

## Input Format
First line of input contains an integer n (1 ≤ n ≤ 100) — the number of names in the list.

Next n lines each contain a string si, consisting of lowercase English letters. The length of each string is between 1 and 100.

## Output Format
Output n lines each containing either "YES" or "NO" (without quotes), depending on whether this string was already present in the stream or not.

You can print each letter in any case (upper or lower).

## Examples
```input
6
tom
lucius
ginny
harry
ginny
harry
```
```output
NO
NO
NO
NO
YES
YES
```
-----
```input
3
a
a
a
```
```output
NO
YES
YES
```

## Note
In test case 1, for i = 5 there exists j = 3 such that si = sj and j < i, which means that answer for i = 5 is "YES".

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
Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping Dumbledore remove the curse. For this, he wants to give Dumbledore exactly x drops of the potion he made.

Value of x is calculated as maximum of p·ai + q·aj + r·ak for given p, q, r and array a1, a2, ... an such that 1 ≤ i ≤ j ≤ k ≤ n. Help Snape find the value of x. Do note that the value of x may be negative.

## Input Format
First line of input contains 4 integers n, p, q, r ( - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105).

Next line of input contains n space separated integers a1, a2, ... an ( - 109 ≤ ai ≤ 109).

## Output Format
Output a single integer the maximum value of p·ai + q·aj + r·ak that can be obtained provided 1 ≤ i ≤ j ≤ k ≤ n.

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

## Note
In the first sample case, we can take i = j = k = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30.

In second sample case, selecting i = j = 1 and k = 5 gives the answer 12.

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
Polycarp loves lowercase letters and dislikes uppercase ones. Once he got a string s consisting only of lowercase and uppercase Latin letters.

Let A be a set of positions in the string. Let's call it pretty if following conditions are met:

- letters on positions from A in the string are all distinct and lowercase;
- there are no uppercase letters in the string which are situated between positions from A (i.e. there is no such j that s[j] is an uppercase letter, and a1 < j < a2 for some a1 and a2 from A).

Write a program that will determine the maximum number of elements in a pretty set of positions.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 200) — length of string s.

The second line contains a string s consisting of lowercase and uppercase Latin letters.

## Output Format
Print maximum number of elements in pretty set of positions for string s.

## Examples
```input
11
aaaaBaabAbA
```
```output
2
```
-----
```input
12
zACaAbbaazzC
```
```output
3
```
-----
```input
3
ABC
```
```output
0
```

## Note
In the first example the desired positions might be 6 and 8 or 7 and 8. Positions 6 and 7 contain letters 'a', position 8 contains letter 'b'. The pair of positions 1 and 8 is not suitable because there is an uppercase letter 'B' between these position.

In the second example desired positions can be 7, 8 and 11. There are other ways to choose pretty set consisting of three elements.

In the third example the given string s does not contain any lowercase letters, so the answer is 0.

Now solve the problem and return the code.