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

# Problem
You are given three integers $$$a$$$, $$$b$$$, $$$k$$$.

Find two binary integers $$$x$$$ and $$$y$$$ ($$$x \ge y$$$) such that

1. both $$$x$$$ and $$$y$$$ consist of $$$a$$$ zeroes and $$$b$$$ ones;
2. $$$x - y$$$ (also written in binary form) has exactly $$$k$$$ ones.

## Input Format
The only line contains three integers $$$a$$$, $$$b$$$, and $$$k$$$ ($$$0 \leq a$$$; $$$1 \leq b$$$; $$$0 \leq k \leq a + b \leq 2 \cdot 10^5$$$) — the number of zeroes, ones, and the number of ones in the result.

## Output Format
If it's possible to find two suitable integers, print "Yes" followed by $$$x$$$ and $$$y$$$ in base-2.

Otherwise print "No".

If there are multiple possible answers, print any of them.

## Examples
```input
4 2 3
```
```output
Yes
101000
100001
```
-----
```input
3 2 1
```
```output
Yes
10100
10010
```
-----
```input
3 2 5
```
```output
No
```

## Note
In the first example, $$$x = 101000_2 = 2^5 + 2^3 = 40_{10}$$$, $$$y = 100001_2 = 2^5 + 2^0 = 33_{10}$$$, $$$40_{10} - 33_{10} = 7_{10} = 2^2 + 2^1 + 2^0 = 111_{2}$$$. Hence $$$x-y$$$ has $$$3$$$ ones in base-2.

In the second example, $$$x = 10100_2 = 2^4 + 2^2 = 20_{10}$$$, $$$y = 10010_2 = 2^4 + 2^1 = 18$$$, $$$x - y = 20 - 18 = 2_{10} = 10_{2}$$$. This is precisely one 1.

In the third example, one may show, that it's impossible to find an answer.

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
You are storing an integer array of length $$$m$$$ in a database. To maintain internal integrity and protect data, the database stores $$$n$$$ copies of this array.

Unfortunately, the recent incident may have altered the stored information in every copy in the database.

It's believed, that the incident altered at most two elements in every copy. You need to recover the original array based on the current state of the database.

In case there are multiple ways to restore the array, report any. If there is no array that differs from every copy in no more than two positions, report that as well.

## Input Format
The first line contains integers $$$n$$$ and $$$m$$$ ($$$2 \le n$$$; $$$1 \le m$$$; $$$n \cdot m \le 250\,000$$$) — the number of copies and the size of the array.

Each of the following $$$n$$$ lines describes one of the currently stored copies in the database, it consists of $$$m$$$ integers $$$s_{i, 1}, s_{i, 2}, \dots, s_{i, m}$$$ ($$$1 \le s_{i, j} \le 10^9$$$).

## Output Format
If there is an array consistent with all given copies, print "Yes" and then the array itself. The array must have length $$$m$$$ and contain integers between $$$1$$$ and $$$10^9$$$ only.

Otherwise, print "No".

If there are multiple possible arrays, print any of them.

## Examples
```input
3 4
1 10 10 100
1 1 1 100
10 100 1 100
```
```output
Yes
1 10 1 100
```
-----
```input
10 7
1 1 1 1 1 1 1
1 1 1 1 1 1 2
1 1 1 1 1 2 2
1 1 1 1 2 2 1
1 1 1 2 2 1 1
1 1 2 2 1 1 1
1 2 2 1 1 1 1
2 2 1 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1
```
```output
Yes
1 1 1 1 1 1 1
```
-----
```input
2 5
2 2 1 1 1
1 1 2 2 2
```
```output
No
```

## Note
In the first example, the array $$$[1, 10, 1, 100]$$$ differs from first and second copies in just one position, and from the third copy in two positions.

In the second example, array $$$[1, 1, 1, 1, 1, 1, 1]$$$ is the same as the first copy and differs from all other copies in at most two positions.

In the third example, there is no array differing in at most two positions from every database's copy.

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
Kawashiro Nitori is a girl who loves competitive programming.

One day she found a string and an integer. As an advanced problem setter, she quickly thought of a problem.

Given a string $$$s$$$ and a parameter $$$k$$$, you need to check if there exist $$$k+1$$$ non-empty strings $$$a_1,a_2...,a_{k+1}$$$, such that $$$$$$s=a_1+a_2+\ldots +a_k+a_{k+1}+R(a_k)+R(a_{k-1})+\ldots+R(a_{1}).$$$$$$

Here $$$+$$$ represents concatenation. We define $$$R(x)$$$ as a reversed string $$$x$$$. For example $$$R(abcd) = dcba$$$. Note that in the formula above the part $$$R(a_{k+1})$$$ is intentionally skipped.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$)  — the number of test cases. The description of the test cases follows.

The first line of each test case description contains two integers $$$n$$$, $$$k$$$ ($$$1\le n\le 100$$$, $$$0\le k\le \lfloor \frac{n}{2} \rfloor$$$)  — the length of the string $$$s$$$ and the parameter $$$k$$$.

The second line of each test case description contains a single string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

## Output Format
For each test case, print "YES" (without quotes), if it is possible to find $$$a_1,a_2,\ldots,a_{k+1}$$$, and "NO" (without quotes) otherwise.

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

## Examples
```input
7
5 1
qwqwq
2 1
ab
3 1
ioi
4 2
icpc
22 0
dokidokiliteratureclub
19 8
imteamshanghaialice
6 3
aaaaaa
```
```output
YES
NO
YES
NO
YES
NO
NO
```

## Note
In the first test case, one possible solution is $$$a_1=qw$$$ and $$$a_2=q$$$.

In the third test case, one possible solution is $$$a_1=i$$$ and $$$a_2=o$$$.

In the fifth test case, one possible solution is $$$a_1=dokidokiliteratureclub$$$.

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 a multiset $$$S$$$ initially consisting of $$$n$$$ distinct non-negative integers. A multiset is a set, that can contain some elements multiple times.

You will perform the following operation $$$k$$$ times:

- Add the element $$$\lceil\frac{a+b}{2}\rceil$$$ (rounded up) into $$$S$$$, where $$$a = \operatorname{mex}(S)$$$ and $$$b = \max(S)$$$. If this number is already in the set, it is added again.

Here $$$\operatorname{max}$$$ of a multiset denotes the maximum integer in the multiset, and $$$\operatorname{mex}$$$ of a multiset denotes the smallest non-negative integer that is not present in the multiset. For example:

- $$$\operatorname{mex}(\{1,4,0,2\})=3$$$;
- $$$\operatorname{mex}(\{2,5,1\})=0$$$.

Your task is to calculate the number of distinct elements in $$$S$$$ after $$$k$$$ operations will be done.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1\le n\le 10^5$$$, $$$0\le k\le 10^9$$$) — the initial size of the multiset $$$S$$$ and how many operations you need to perform.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_i\le 10^9$$$) — the numbers in the initial multiset.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, print the number of distinct elements in $$$S$$$ after $$$k$$$ operations will be done.

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

## Note
In the first test case, $$$S=\{0,1,3,4\}$$$, $$$a=\operatorname{mex}(S)=2$$$, $$$b=\max(S)=4$$$, $$$\lceil\frac{a+b}{2}\rceil=3$$$. So $$$3$$$ is added into $$$S$$$, and $$$S$$$ becomes $$$\{0,1,3,3,4\}$$$. The answer is $$$4$$$.

In the second test case, $$$S=\{0,1,4\}$$$, $$$a=\operatorname{mex}(S)=2$$$, $$$b=\max(S)=4$$$, $$$\lceil\frac{a+b}{2}\rceil=3$$$. So $$$3$$$ is added into $$$S$$$, and $$$S$$$ becomes $$$\{0,1,3,4\}$$$. The answer is $$$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: 64.0 MB

# Problem
A new cottage village called «Flatville» is being built in Flatland. By now they have already built in «Flatville» n square houses with the centres on the Оx-axis. The houses' sides are parallel to the coordinate axes. It's known that no two houses overlap, but they can touch each other.

The architect bureau, where Peter works, was commissioned to build a new house in «Flatville». The customer wants his future house to be on the Оx-axis, to be square in shape, have a side t, and touch at least one of the already built houses. For sure, its sides should be parallel to the coordinate axes, its centre should be on the Ox-axis and it shouldn't overlap any of the houses in the village.

Peter was given a list of all the houses in «Flatville». Would you help him find the amount of possible positions of the new house?

## Input Format
The first line of the input data contains numbers n and t (1 ≤ n, t ≤ 1000). Then there follow n lines, each of them contains two space-separated integer numbers: xi ai, where xi — x-coordinate of the centre of the i-th house, and ai — length of its side ( - 1000 ≤ xi ≤ 1000, 1 ≤ ai ≤ 1000).

## Output Format
Output the amount of possible positions of the new house.

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

## Note
It is possible for the x-coordinate of the new house to have non-integer value.

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

# Problem
Petya is the most responsible worker in the Research Institute. So he was asked to make a very important experiment: to melt the chocolate bar with a new laser device. The device consists of a rectangular field of n × m cells and a robotic arm. Each cell of the field is a 1 × 1 square. The robotic arm has two lasers pointed at the field perpendicularly to its surface. At any one time lasers are pointed at the centres of some two cells. Since the lasers are on the robotic hand, their movements are synchronized — if you move one of the lasers by a vector, another one moves by the same vector.

The following facts about the experiment are known:

- initially the whole field is covered with a chocolate bar of the size n × m, both lasers are located above the field and are active;
- the chocolate melts within one cell of the field at which the laser is pointed;
- all moves of the robotic arm should be parallel to the sides of the field, after each move the lasers should be pointed at the centres of some two cells;
- at any one time both lasers should be pointed at the field. Petya doesn't want to become a second Gordon Freeman.

You are given n, m and the cells (x1, y1) and (x2, y2), where the lasers are initially pointed at (xi is a column number, yi is a row number). Rows are numbered from 1 to m from top to bottom and columns are numbered from 1 to n from left to right. You are to find the amount of cells of the field on which the chocolate can't be melted in the given conditions.

## Input Format
The first line contains one integer number t (1 ≤ t ≤ 10000) — the number of test sets. Each of the following t lines describes one test set. Each line contains integer numbers n, m, x1, y1, x2, y2, separated by a space (2 ≤ n, m ≤ 109, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m). Cells (x1, y1) and (x2, y2) are distinct.

## Output Format
Each of the t lines of the output should contain the answer to the corresponding input test set.

## Examples
```input
2
4 4 1 1 3 3
4 3 1 1 2 2
```
```output
8
2
```

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

# Problem
Last summer Peter was at his granny's in the country, when a wolf attacked sheep in the nearby forest. Now he fears to walk through the forest, to walk round the forest, even to get out of the house. He explains this not by the fear of the wolf, but by a strange, in his opinion, pattern of the forest that has n levels, where n is an even number.

In the local council you were given an area map, where the granny's house is marked by point H, parts of dense forest are marked grey (see the picture to understand better).

After a long time at home Peter decided to yield to his granny's persuasions and step out for a breath of fresh air. Being prudent, Peter plans the route beforehand. The route, that Peter considers the most suitable, has the following characteristics:

- it starts and ends in the same place — the granny's house;
- the route goes along the forest paths only (these are the segments marked black in the picture);
- the route has positive length (to step out for a breath of fresh air Peter has to cover some distance anyway);
- the route cannot cross itself;
- there shouldn't be any part of dense forest within the part marked out by this route;

You should find the amount of such suitable oriented routes modulo 1000000009.

The example of the area map for n = 12 is given in the picture. Since the map has a regular structure, you can construct it for other n by analogy using the example.

## Input Format
The input data contain the only even integer n (2 ≤ n ≤ 106).

## Output Format
Output the only number — the amount of Peter's routes modulo 1000000009.

## Examples
```input
2
```
```output
10
```
-----
```input
4
```
```output
74
```

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
This winter is so cold in Nvodsk! A group of n friends decided to buy k bottles of a soft drink called "Take-It-Light" to warm up a bit. Each bottle has l milliliters of the drink. Also they bought c limes and cut each of them into d slices. After that they found p grams of salt.

To make a toast, each friend needs nl milliliters of the drink, a slice of lime and np grams of salt. The friends want to make as many toasts as they can, provided they all drink the same amount. How many toasts can each friend make?

## Input Format
The first and only line contains positive integers n, k, l, c, d, p, nl, np, not exceeding 1000 and no less than 1. The numbers are separated by exactly one space.

## Output Format
Print a single integer — the number of toasts each friend can make.

## Examples
```input
3 4 5 10 8 100 3 1
```
```output
2
```
-----
```input
5 100 10 1 19 90 4 3
```
```output
3
```
-----
```input
10 1000 1000 25 23 1 50 1
```
```output
0
```

## Note
A comment to the first sample:

Overall the friends have 4 * 5 = 20 milliliters of the drink, it is enough to make 20 / 3 = 6 toasts. The limes are enough for 10 * 8 = 80 toasts and the salt is enough for 100 / 1 = 100 toasts. However, there are 3 friends in the group, so the answer is min(6, 80, 100) / 3 = 2.

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
I, Fischl, Prinzessin der Verurteilung, descend upon this land by the call of fate an — Oh, you are also a traveler from another world? Very well, I grant you permission to travel with me.

It is no surprise Fischl speaks with a strange choice of words. However, this time, not even Oz, her raven friend, can interpret her expressions! Maybe you can help us understand what this young princess is saying?

You are given a string of $$$n$$$ lowercase Latin letters, the word that Fischl just spoke. You think that the MEX of this string may help you find the meaning behind this message. The MEX of the string is defined as the shortest string that doesn't appear as a contiguous substring in the input. If multiple strings exist, the lexicographically smallest one is considered the MEX. Note that the empty substring does NOT count as a valid MEX.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Find out what the MEX of the string is!

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 1000$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the length of the word. The second line for each test case contains a single string of $$$n$$$ lowercase Latin letters.

The sum of $$$n$$$ over all test cases will not exceed $$$1000$$$.

## Output Format
For each test case, output the MEX of the string on a new line.

## Examples
```input
3
28
qaabzwsxedcrfvtgbyhnujmiklop
13
cleanairactbd
10
aannttoonn
```
```output
ac
f
b
```

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
Omkar's most recent follower, Ajit, has entered the Holy Forest. Ajit realizes that Omkar's forest is an $$$n$$$ by $$$m$$$ grid ($$$1 \leq n, m \leq 2000$$$) of some non-negative integers. Since the forest is blessed by Omkar, it satisfies some special conditions:

1. For any two adjacent (sharing a side) cells, the absolute value of the difference of numbers in them is at most $$$1$$$.
2. If the number in some cell is strictly larger than $$$0$$$, it should be strictly greater than the number in at least one of the cells adjacent to it.

Unfortunately, Ajit is not fully worthy of Omkar's powers yet. He sees each cell as a "0" or a "#". If a cell is labeled as "0", then the number in it must equal $$$0$$$. Otherwise, the number in it can be any nonnegative integer.

Determine how many different assignments of elements exist such that these special conditions are satisfied. Two assignments are considered different if there exists at least one cell such that the numbers written in it in these assignments are different. Since the answer may be enormous, find the answer modulo $$$10^9+7$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 100$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2000, nm \geq 2$$$) – the dimensions of the forest.

$$$n$$$ lines follow, each consisting of one string of $$$m$$$ characters. Each of these characters is either a "0" or a "#".

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2000$$$.

## Output Format
For each test case, print one integer: the number of valid configurations modulo $$$10^9+7$$$.

## Examples
```input
4
3 4
0000
00#0
0000
2 1
#
#
1 2
##
6 29
#############################
#000##0###0##0#0####0####000#
#0#0##00#00##00####0#0###0#0#
#0#0##0#0#0##00###00000##00##
#000##0###0##0#0##0###0##0#0#
#############################
```
```output
2
3
3
319908071
```

## Note
For the first test case, the two valid assignments are

$$$0000\\ 0000\\ 0000$$$

and

$$$0000\\ 0010\\ 0000$$$

Now solve the problem and return the code.