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: 10.0 seconds
Memory limit: 1024.0 MB

# Problem
For a permutation $$$p$$$ of numbers $$$1$$$ through $$$n$$$, we define a stair array $$$a$$$ as follows: $$$a_i$$$ is length of the longest segment of permutation which contains position $$$i$$$ and is made of consecutive values in sorted order: $$$[x, x+1, \ldots, y-1, y]$$$ or $$$[y, y-1, \ldots, x+1, x]$$$ for some $$$x \leq y$$$. For example, for permutation $$$p = [4, 1, 2, 3, 7, 6, 5]$$$ we have $$$a = [1, 3, 3, 3, 3, 3, 3]$$$.

You are given the stair array $$$a$$$. Your task is to calculate the number of permutations which have stair array equal to $$$a$$$. Since the number can be big, compute it modulo $$$998\,244\,353$$$. Note that this number can be equal to zero.

## Input Format
The first line of input contains integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  — the length of a stair array $$$a$$$.

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

## Output Format
Print the number of permutations which have stair array equal to $$$a$$$. Since the number can be big, compute it modulo $$$998\,244\,353$$$.

## Examples
```input
6
3 3 3 1 1 1
```
```output
6
```
-----
```input
7
4 4 4 4 3 3 3
```
```output
6
```
-----
```input
1
1
```
```output
1
```
-----
```input
8
2 2 2 2 2 2 1 1
```
```output
370
```
-----
```input
4
3 2 3 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
Moamen has an array of $$$n$$$ distinct integers. He wants to sort that array in non-decreasing order by doing the following operations in order exactly once:

1. Split the array into exactly $$$k$$$ non-empty subarrays such that each element belongs to exactly one subarray.
2. Reorder these subarrays arbitrary.
3. Merge the subarrays in their new order.

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

Can you tell Moamen if there is a way to sort the array in non-decreasing order using the operations written above?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le |a_i| \le 10^9$$$). It is guaranteed that all numbers are distinct.

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

## Output Format
For each test case, you should output a single string.

If Moamen can sort the array in non-decreasing order, output "YES" (without quotes). Otherwise, output "NO" (without quotes).

You can print each letter of "YES" and "NO" in any case (upper or lower).

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

## Note
In the first test case, $$$a = [6, 3, 4, 2, 1]$$$, and $$$k = 4$$$, so we can do the operations as follows:

1. Split $$$a$$$ into $$$\{ [6], [3, 4], [2], [1] \}$$$.
2. Reorder them: $$$\{ [1], [2], [3,4], [6] \}$$$.
3. Merge them: $$$[1, 2, 3, 4, 6]$$$, so now the array is sorted.

In the second test case, there is no way to sort the array by splitting it into only $$$2$$$ subarrays.

As an example, if we split it into $$$\{ [1, -4], [0, -2] \}$$$, we can reorder them into $$$\{ [1, -4], [0, -2] \}$$$ or $$$\{ [0, -2], [1, -4] \}$$$. However, after merging the subarrays, it is impossible to get a sorted array.

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
Moamen and Ezzat are playing a game. They create an array $$$a$$$ of $$$n$$$ non-negative integers where every element is less than $$$2^k$$$.

Moamen wins if $$$a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$$$.

Here $$$\&$$$ denotes the bitwise AND operation, and $$$\oplus$$$ denotes the bitwise XOR operation.

Please calculate the number of winning for Moamen arrays $$$a$$$.

As the result may be very large, print the value modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5$$$)— the number of test cases.

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n\le 2\cdot 10^5$$$, $$$0 \le k \le 2\cdot 10^5$$$).

## Output Format
For each test case, print a single value — the number of different arrays that Moamen wins with.

Print the result modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

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

## Note
In the first example, $$$n = 3$$$, $$$k = 1$$$. As a result, all the possible arrays are $$$[0,0,0]$$$, $$$[0,0,1]$$$, $$$[0,1,0]$$$, $$$[1,0,0]$$$, $$$[1,1,0]$$$, $$$[0,1,1]$$$, $$$[1,0,1]$$$, and $$$[1,1,1]$$$.

Moamen wins in only $$$5$$$ of them: $$$[0,0,0]$$$, $$$[1,1,0]$$$, $$$[0,1,1]$$$, $$$[1,0,1]$$$, and $$$[1,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
During the hypnosis session, Nicholas suddenly remembered a positive integer $$$n$$$, which doesn't contain zeros in decimal notation.

Soon, when he returned home, he got curious: what is the maximum number of digits that can be removed from the number so that the number becomes not prime, that is, either composite or equal to one?

For some numbers doing so is impossible: for example, for number $$$53$$$ it's impossible to delete some of its digits to obtain a not prime integer. However, for all $$$n$$$ in the test cases of this problem, it's guaranteed that it's possible to delete some of their digits to obtain a not prime number.

Note that you cannot remove all the digits from the number.

A prime number is a number that has no divisors except one and itself. A composite is a number that has more than two divisors. $$$1$$$ is neither a prime nor a composite number.

## Input Format
Each test contains multiple test cases.

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 10^3$$$), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer $$$k$$$ ($$$1 \le k \le 50$$$) — the number of digits in the number.

The second line of each test case contains a positive integer $$$n$$$, which doesn't contain zeros in decimal notation ($$$10^{k-1} \le n < 10^{k}$$$). It is guaranteed that it is always possible to remove less than $$$k$$$ digits to make the number not prime.

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

## Output Format
For every test case, print two numbers in two lines. In the first line print the number of digits, that you have left in the number. In the second line print the digits left after all delitions.

If there are multiple solutions, print any.

## Examples
```input
7
3
237
5
44444
3
221
2
35
3
773
1
4
30
626221626221626221626221626221
```
```output
2
27
1
4
1
1
2
35
2
77
1
4
1
6
```

## Note
In the first test case, you can't delete $$$2$$$ digits from the number $$$237$$$, as all the numbers $$$2$$$, $$$3$$$, and $$$7$$$ are prime. However, you can delete $$$1$$$ digit, obtaining a number $$$27 = 3^3$$$.

In the second test case, you can delete all digits except one, as $$$4 = 2^2$$$ is a composite number.

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
After crossing the Windswept Wastes, Ori has finally reached the Windtorn Ruins to find the Heart of the Forest! However, the ancient repository containing this priceless Willow light did not want to open!

Ori was taken aback, but the Voice of the Forest explained to him that the cunning Gorleks had decided to add protection to the repository.

The Gorleks were very fond of the "string expansion" operation. They were also very fond of increasing subsequences.

Suppose a string $$$s_1s_2s_3 \ldots s_n$$$ is given. Then its "expansion" is defined as the sequence of strings $$$s_1$$$, $$$s_1 s_2$$$, ..., $$$s_1 s_2 \ldots s_n$$$, $$$s_2$$$, $$$s_2 s_3$$$, ..., $$$s_2 s_3 \ldots s_n$$$, $$$s_3$$$, $$$s_3 s_4$$$, ..., $$$s_{n-1} s_n$$$, $$$s_n$$$. For example, the "expansion" the string 'abcd' will be the following sequence of strings: 'a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd'.

To open the ancient repository, Ori must find the size of the largest increasing subsequence of the "expansion" of the string $$$s$$$. Here, strings are compared lexicographically.

Help Ori with this task!

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$$$.

## Input Format
Each test contains multiple test cases.

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 10^3$$$), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer $$$n$$$ ($$$1 \le n \le 5000$$$) — length of the string.

The second line of each test case contains a non-empty string of length $$$n$$$, which consists of lowercase latin letters.

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

## Output Format
For every test case print one non-negative integer — the answer to the problem.

## Examples
```input
7
5
acbac
8
acabacba
12
aaaaaaaaaaaa
10
abacabadac
8
dcbaabcd
3
cba
6
sparky
```
```output
9
17
12
29
14
3
9
```

## Note
In first test case the "expansion" of the string is: 'a', 'ac', 'acb', 'acba', 'acbac', 'c', 'cb', 'cba', 'cbac', 'b', 'ba', 'bac', 'a', 'ac', 'c'. The answer can be, for example, 'a', 'ac', 'acb', 'acba', 'acbac', 'b', 'ba', 'bac', 'c'.

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 two positive integers $$$n$$$ and $$$s$$$. Find the maximum possible median of an array of $$$n$$$ non-negative integers (not necessarily distinct), such that the sum of its elements is equal to $$$s$$$.

A median of an array of integers of length $$$m$$$ is the number standing on the $$$\lceil {\frac{m}{2}} \rceil$$$-th (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting from $$$1$$$. For example, a median of the array $$$[20,40,20,50,50,30]$$$ is the $$$\lceil \frac{m}{2} \rceil$$$-th element of $$$[20,20,30,40,50,50]$$$, so it is $$$30$$$. There exist other definitions of the median, but in this problem we use the described definition.

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

Each test case contains a single line with two integers $$$n$$$ and $$$s$$$ ($$$1 \le n, s \le 10^9$$$) — the length of the array and the required sum of the elements.

## Output Format
For each test case print a single integer — the maximum possible median.

## Examples
```input
8
1 5
2 5
3 5
2 1
7 17
4 14
1 1000000000
1000000000 1
```
```output
5
2
2
0
4
4
1000000000
0
```

## Note
Possible arrays for the first three test cases (in each array the median is underlined):

- In the first test case $$$[\underline{5}]$$$
- In the second test case $$$[\underline{2}, 3]$$$
- In the third test case $$$[1, \underline{2}, 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: 256.0 MB

# Problem
A binary string is a string that consists of characters $$$0$$$ and $$$1$$$.

Let $$$\operatorname{MEX}$$$ of a binary string be the smallest digit among $$$0$$$, $$$1$$$, or $$$2$$$ that does not occur in the string. For example, $$$\operatorname{MEX}$$$ of $$$001011$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ occur in the string at least once, $$$\operatorname{MEX}$$$ of $$$1111$$$ is $$$0$$$, because $$$0$$$ and $$$2$$$ do not occur in the string and $$$0 < 2$$$.

A binary string $$$s$$$ is given. You should cut it into any number of substrings such that each character is in exactly one substring. It is possible to cut the string into a single substring — the whole string.

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.

What is the minimal sum of $$$\operatorname{MEX}$$$ of all substrings pieces can be?

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

Each test case contains a single binary string $$$s$$$ ($$$1 \le |s| \le 10^5$$$).

It's guaranteed that the sum of lengths of $$$s$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case print a single integer — the minimal sum of $$$\operatorname{MEX}$$$ of all substrings that it is possible to get by cutting $$$s$$$ optimally.

## Examples
```input
6
01
1111
01100
101
0000
01010
```
```output
1
0
2
1
1
2
```

## Note
In the first test case the minimal sum is $$$\operatorname{MEX}(0) + \operatorname{MEX}(1) = 1 + 0 = 1$$$.

In the second test case the minimal sum is $$$\operatorname{MEX}(1111) = 0$$$.

In the third test case the minimal sum is $$$\operatorname{MEX}(01100) = 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: 256.0 MB

# Problem
This problem is a simplified version of D2, but it has significant differences, so read the whole statement.

Polycarp has an array of $$$n$$$ ($$$n$$$ is even) integers $$$a_1, a_2, \dots, a_n$$$. Polycarp conceived of a positive integer $$$k$$$. After that, Polycarp began performing the following operations on the array: take an index $$$i$$$ ($$$1 \le i \le n$$$) and reduce the number $$$a_i$$$ by $$$k$$$.

After Polycarp performed some (possibly zero) number of such operations, it turned out that all numbers in the array became the same. Find the maximum $$$k$$$ at which such a situation is possible, or print $$$-1$$$ if such a number can be arbitrarily large.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of two lines. The first line contains an even integer $$$n$$$ ($$$4 \le n \le 40$$$) ($$$n$$$ is even). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$).

It is guaranteed that the sum of all $$$n$$$ specified in the given test cases does not exceed $$$100$$$.

## Output Format
For each test case output on a separate line an integer $$$k$$$ ($$$k \ge 1$$$) — the maximum possible number that Polycarp used in operations on the array, or $$$-1$$$, if such a number can be arbitrarily large.

## Examples
```input
3
6
1 5 3 1 1 5
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
```
```output
2
1
1100
```

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
This problem is a complicated version of D1, but it has significant differences, so read the whole statement.

Polycarp has an array of $$$n$$$ ($$$n$$$ is even) integers $$$a_1, a_2, \dots, a_n$$$. Polycarp conceived of a positive integer $$$k$$$. After that, Polycarp began performing the following operations on the array: take an index $$$i$$$ ($$$1 \le i \le n$$$) and reduce the number $$$a_i$$$ by $$$k$$$.

After Polycarp performed some (possibly zero) number of such operations, it turned out that at least half of the numbers in the array became the same. Find the maximum $$$k$$$ at which such a situation is possible, or print $$$-1$$$ if such a number can be arbitrarily large.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of two lines. The first line contains an even integer $$$n$$$ ($$$4 \le n \le 40$$$) ($$$n$$$ is even). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$).

It is guaranteed that the sum of all $$$n$$$ specified in the given test cases does not exceed $$$100$$$.

## Output Format
For each test case output on a separate line an integer $$$k$$$ ($$$k \ge 1$$$) — the maximum possible number that Polycarp used in operations on the array, or $$$-1$$$, if such a number can be arbitrarily large.

## Examples
```input
4
6
48 13 22 -15 16 35
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
4
1 1 1 1
```
```output
13
2
-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: 2.0 seconds
Memory limit: 64.0 MB

# Problem
According to a new ISO standard, a flag of every country should have a chequered field n × m, each square should be of one of 10 colours, and the flag should be «striped»: each horizontal row of the flag should contain squares of the same colour, and the colours of adjacent horizontal rows should be different. Berland's government asked you to find out whether their flag meets the new ISO standard.

## Input Format
The first line of the input contains numbers n and m (1 ≤ n, m ≤ 100), n — the amount of rows, m — the amount of columns on the flag of Berland. Then there follows the description of the flag: each of the following n lines contain m characters. Each character is a digit between 0 and 9, and stands for the colour of the corresponding square.

## Output Format
Output YES, if the flag meets the new ISO standard, and NO otherwise.

## Examples
```input
3 3
000
111
222
```
```output
YES
```
-----
```input
3 3
000
000
111
```
```output
NO
```
-----
```input
3 3
000
111
002
```
```output
NO
```

Now solve the problem and return the code.