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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
Petya is a big fan of mathematics, especially its part related to fractions. Recently he learned that a fraction $$\frac{a}{b}$$ is called proper iff its numerator is smaller than its denominator (a < b) and that the fraction is called irreducible if its numerator and its denominator are coprime (they do not have positive common divisors except 1).

During his free time, Petya thinks about proper irreducible fractions and converts them to decimals using the calculator. One day he mistakenly pressed addition button ( + ) instead of division button (÷) and got sum of numerator and denominator that was equal to n instead of the expected decimal notation.

Petya wanted to restore the original fraction, but soon he realized that it might not be done uniquely. That's why he decided to determine maximum possible proper irreducible fraction $$\frac{a}{b}$$ such that sum of its numerator and denominator equals n. Help Petya deal with this problem.

## Input Format
In the only line of input there is an integer n (3 ≤ n ≤ 1000), the sum of numerator and denominator of the fraction.

## Output Format
Output two space-separated positive integers a and b, numerator and denominator of the maximum possible proper irreducible fraction satisfying the given sum.

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

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
Maxim wants to buy an apartment in a new house at Line Avenue of Metropolis. The house has n apartments that are numbered from 1 to n and are arranged in a row. Two apartments are adjacent if their indices differ by 1. Some of the apartments can already be inhabited, others are available for sale.

Maxim often visits his neighbors, so apartment is good for him if it is available for sale and there is at least one already inhabited apartment adjacent to it. Maxim knows that there are exactly k already inhabited apartments, but he doesn't know their indices yet.

Find out what could be the minimum possible and the maximum possible number of apartments that are good for Maxim.

## Input Format
The only line of the input contains two integers: n and k (1 ≤ n ≤ 109, 0 ≤ k ≤ n).

## Output Format
Print the minimum possible and the maximum possible number of apartments good for Maxim.

## Examples
```input
6 3
```
```output
1 3
```

## Note
In the sample test, the number of good apartments could be minimum possible if, for example, apartments with indices 1, 2 and 3 were inhabited. In this case only apartment 4 is good. The maximum possible number could be, for example, if apartments with indices 1, 3 and 5 were inhabited. In this case all other apartments: 2, 4 and 6 are good.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
n people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person from the line, and so on. They play until someone wins k games in a row. This player becomes the winner.

For each of the participants, you know the power to play table tennis, and for all players these values are different. In a game the player with greater power always wins. Determine who will be the winner.

## Input Format
The first line contains two integers: n and k (2 ≤ n ≤ 500, 2 ≤ k ≤ 1012) — the number of people and the number of wins.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n) — powers of the player. It's guaranteed that this line contains a valid permutation, i.e. all ai are distinct.

## Output Format
Output a single integer — power of the winner.

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

## Note
Games in the second sample:

3 plays with 1. 3 wins. 1 goes to the end of the line.

3 plays with 2. 3 wins. He wins twice in a row. He becomes the winner.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Ivan has a robot which is situated on an infinite grid. Initially the robot is standing in the starting cell (0, 0). The robot can process commands. There are four types of commands it can perform:

- U — move from the cell (x, y) to (x, y + 1);
- D — move from (x, y) to (x, y - 1);
- L — move from (x, y) to (x - 1, y);
- R — move from (x, y) to (x + 1, y).

Ivan entered a sequence of n commands, and the robot processed it. After this sequence the robot ended up in the starting cell (0, 0), but Ivan doubts that the sequence is such that after performing it correctly the robot ends up in the same cell. He thinks that some commands were ignored by robot. To acknowledge whether the robot is severely bugged, he needs to calculate the maximum possible number of commands that were performed correctly. Help Ivan to do the calculations!

## Input Format
The first line contains one number n — the length of sequence of commands entered by Ivan (1 ≤ n ≤ 100).

The second line contains the sequence itself — a string consisting of n characters. Each character can be U, D, L or R.

## Output Format
Print the maximum possible number of commands from the sequence the robot could perform to end up in the starting cell.

## Examples
```input
4
LDUR
```
```output
4
```
-----
```input
5
RRRUU
```
```output
0
```
-----
```input
6
LLRRRR
```
```output
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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string s consisting of lowercase Latin letters. Character c is called k-dominant iff each substring of s with length at least k contains this character c.

You have to find minimum k such that there exists at least one k-dominant character.

## Input Format
The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 100000).

## Output Format
Print one number — the minimum value of k such that there exists at least one k-dominant character.

## Examples
```input
abacaba
```
```output
2
```
-----
```input
zzzzz
```
```output
1
```
-----
```input
abcde
```
```output
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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A permutation p of size n is an array such that every integer from 1 to n occurs exactly once in this array.

Let's call a permutation an almost identity permutation iff there exist at least n - k indices i (1 ≤ i ≤ n) such that pi = i.

Your task is to count the number of almost identity permutations for given numbers n and k.

## Input Format
The first line contains two integers n and k (4 ≤ n ≤ 1000, 1 ≤ k ≤ 4).

## Output Format
Print the number of almost identity permutations for given n and k.

## Examples
```input
4 1
```
```output
1
```
-----
```input
4 2
```
```output
7
```
-----
```input
5 3
```
```output
31
```
-----
```input
5 4
```
```output
76
```

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array a consisting of n integers, and additionally an integer m. You have to choose some sequence of indices b1, b2, ..., bk (1 ≤ b1 < b2 < ... < bk ≤ n) in such a way that the value of $$\sum_{i=1}^{k} a_{b_i} \bmod m$$ is maximized. Chosen sequence can be empty.

Print the maximum possible value of $$\sum_{i=1}^{k} a_{b_i} \bmod m$$.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ 35, 1 ≤ m ≤ 109).

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

## Output Format
Print the maximum possible value of $$\sum_{i=1}^{k} a_{b_i} \bmod m$$.

## Examples
```input
4 4
5 2 4 1
```
```output
3
```
-----
```input
3 20
199 41 299
```
```output
19
```

## Note
In the first example you can choose a sequence b = {1, 2}, so the sum $$\sum_{i=1}^{k}a_{bi}$$ is equal to 7 (and that's 3 after taking it modulo 4).

In the second example you can choose a sequence b = {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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a connected undirected graph with n vertices and m edges. The vertices are enumerated from 1 to n.

You are given n integers c1, c2, ..., cn, each of them is between  - n and n, inclusive. It is also guaranteed that the parity of cv equals the parity of degree of vertex v. The degree of a vertex is the number of edges connected to it.

You are to write a weight between  - 2·n2 and 2·n2 (inclusive) on each edge in such a way, that for each vertex v the sum of weights on edges connected to this vertex is equal to cv, or determine that this is impossible.

## Input Format
The first line contains two integers n and m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 105) — the number of vertices and the number of edges.

The next line contains n integers c1, c2, ..., cn ( - n ≤ ci ≤ n), where ci is the required sum of weights of edges connected to vertex i. It is guaranteed that the parity of ci equals the parity of degree of vertex i.

The next m lines describe edges of the graph. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), meaning that the i-th edge connects vertices ai and bi.

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

## Output Format
If there is no solution, print "NO".

Otherwise print "YES" and then m lines, the i-th of them is the weight of the i-th edge wi ( - 2·n2 ≤ wi ≤ 2·n2).

## Examples
```input
3 3
2 2 2
1 2
2 3
1 3
```
```output
YES
1
1
1
```
-----
```input
4 3
-1 0 2 1
1 2
2 3
3 4
```
```output
YES
-1
1
1
```
-----
```input
6 6
3 5 5 5 1 5
1 4
3 2
4 3
4 5
3 5
5 6
```
```output
YES
3
5
3
-1
-3
5
```
-----
```input
4 4
4 4 2 4
1 2
2 3
3 4
4 1
```
```output
NO
```

Now solve the problem and return the code.