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

# Problem
You are given three non-negative integers $$$n$$$, $$$k$$$, and $$$x$$$. Find the maximum possible sum of elements in an array consisting of non-negative integers, which has $$$n$$$ elements, its MEX is equal to $$$k$$$, and all its elements do not exceed $$$x$$$. If such an array does not exist, output $$$-1$$$.

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

- The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
- The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
- The MEX of $$$[0,3,1,2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the array, but $$$4$$$ does not.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Then follows the description of the test cases.

The only line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$x$$$ ($$$1 \leq n, k, x \leq 200$$$).

## Output Format
For each test case, output a single number — the maximum sum of elements in a valid array, or $$$-1$$$, if such an array does not exist.

## Examples
```input
9
5 3 3
4 7 5
4 2 28
12 10 6
57 51 122
200 1 200
2 2 1
3 2 1
4 7 10
```
```output
7
-1
57
-1
2007
39800
1
2
-1
```

## Note
In the first test case, the maximum sum is $$$7$$$, and one of the valid arrays is $$$[0, 1, 2, 2, 2]$$$.

In the second test case, there are no valid arrays of length $$$n$$$.

In the third test case, the maximum sum is $$$57$$$, and one of the valid arrays is $$$[0, 1, 28, 28]$$$.

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 two arrays of integers — $$$a_1, \ldots, a_n$$$ of length $$$n$$$, and $$$b_1, \ldots, b_m$$$ of length $$$m$$$. You can choose any element $$$b_j$$$ from array $$$b$$$ ($$$1 \leq j \leq m$$$), and for all $$$1 \leq i \leq n$$$ perform $$$a_i = a_i | b_j$$$. You can perform any number of such operations.

After all the operations, the value of $$$x = a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$ will be calculated. Find the minimum and maximum values of $$$x$$$ that could be obtained after performing any set of operations.

Above, $$$|$$$ is the bitwise OR operation, and $$$\oplus$$$ is the bitwise XOR operation.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. This is followed by the description of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — the sizes of arrays $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the array $$$a$$$.

The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq b_i \leq 10^9$$$) — the array $$$b$$$.

It is guaranteed that the sum of values of $$$n$$$ and $$$m$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output $$$2$$$ numbers: the minimum and maximum possible values of $$$x$$$ after performing any set of operations.

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

## Note
In the first test case, if we apply the operation with element $$$b_1 = 1$$$, the array $$$a$$$ will become $$$[1, 1]$$$, and $$$x$$$ will be $$$0$$$. If no operations are applied, then $$$x = 1$$$.

In the second test case, if no operations are applied, then $$$x = 2$$$. If we apply the operation with $$$b_1 = 1$$$, then $$$a = [1, 1, 3]$$$, and $$$x = 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$n$$$ and $$$k$$$. You are also given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of size $$$n$$$. It is known that for all $$$1 \leq i \leq n$$$, $$$1 \leq a_i \leq k$$$.

Define a two-dimensional array $$$b$$$ of size $$$n \times n$$$ as follows: $$$b_{i, j} = \min(a_i, a_j)$$$. Represent array $$$b$$$ as a square, where the upper left cell is $$$b_{1, 1}$$$, rows are numbered from top to bottom from $$$1$$$ to $$$n$$$, and columns are numbered from left to right from $$$1$$$ to $$$n$$$. Let the color of a cell be the number written in it (for a cell with coordinates $$$(i, j)$$$, this is $$$b_{i, j}$$$).

For each color from $$$1$$$ to $$$k$$$, find the smallest rectangle in the array $$$b$$$ containing all cells of this color. Output the sum of width and height of this rectangle.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n, k \leq 10^5$$$) — the size of array $$$a$$$ and the number of colors.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq k$$$) — the array $$$a$$$.

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

## Output Format
For each test case, output $$$k$$$ numbers: the sums of width and height of the smallest rectangle containing all cells of a color, for each color from $$$1$$$ to $$$k$$$.

## Examples
```input
5
2 1
1 1
2 2
1 2
3 5
3 2 4
4 2
1 2 1 2
5 3
1 2 3 2 1
```
```output
4 
4 2 
0 6 6 2 0 
8 6 
10 6 2
```

## Note
In the first test case, the entire array $$$b$$$ consists of color $$$1$$$, so the smallest rectangle for color $$$1$$$ has a size of $$$2 \times 2$$$, and the sum of its sides is $$$4$$$.

In the second test case, the array $$$b$$$ looks like this:

1112

One of the corner cells has color $$$2$$$, and the other three cells have color $$$1$$$. Therefore, the smallest rectangle for color $$$1$$$ has a size of $$$2 \times 2$$$, and for color $$$2$$$ it is $$$1 \times 1$$$.

In the last test case, the array $$$b$$$ looks like this:

1111112221123211222111111

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 of integers $$$a$$$ of size $$$n$$$. You can choose a set of non-overlapping subarrays of the given array (note that some elements may be not included in any subarray, this is allowed). For each selected subarray, calculate the MEX of its elements, and then calculate the bitwise XOR of all the obtained MEX values. What is the maximum bitwise XOR that can be obtained?

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

- The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
- The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
- The MEX of $$$[0,3,1,2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the array, but $$$4$$$ does not.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases. This is followed by the description of the test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$) — the array $$$a$$$.

It is guaranteed that the sum of all $$$n$$$ values across all test cases does not exceed $$$5000$$$.

## Output Format
For each test case, output a single number — the maximum possible XOR of the MEX values of the selected subarrays.

## Examples
```input
4
2
1 0
10
1 2 0 7 1 2 0 2 4 3
10
2 1 0 7 1 2 0 2 4 3
3
1 2 1
```
```output
2
6
7
0
```

## Note
In the first test case, the maximum XOR is $$$2$$$ if we take the entire array, $$$\operatorname{MEX}([1, 0]) = 2$$$.

In the second test case, the maximum XOR is $$$6$$$ if we partition the array into segments $$$[1, 2, 0]$$$ and $$$[7, 1, 2, 0, 2, 4, 3]$$$:

- $$$\operatorname{MEX}([1, 2, 0]) = 3$$$,
- $$$\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,

In the third test case, the maximum XOR is $$$7$$$ if we partition the array into segments $$$[1, 0]$$$ and $$$[7, 1, 2, 0, 2, 4, 3]$$$:

- $$$\operatorname{MEX}([1, 0]) = 2$$$,
- $$$\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,

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

# Problem
You are given positive integers $$$n$$$ and $$$k$$$. For each number from $$$1$$$ to $$$n$$$, we write its representation in the number system with base $$$k$$$ (without leading zeros) and then sort the resulting array in lexicographic order as strings. In the sorted array, we number the elements from $$$1$$$ to $$$n$$$ (i.e., indexing starts from $$$1$$$). Find the number of values $$$i$$$ such that the representation of number $$$i$$$ is at the $$$i$$$-th position in the sorted array of representations.

Examples of representations: $$$1$$$ in any number system is equal to $$$1$$$, $$$7$$$ with $$$k = 3$$$ is written as $$$21$$$, and $$$81$$$ with $$$k = 9$$$ is written as $$$100$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases. This is followed by a description of the test cases.

The only line of each test case contains integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$2 \leq k \leq 10^{18}$$$).

## Output Format
For each test case, output a single integer — the number of values $$$1 \leq i \leq n$$$ such that the representation of number $$$i$$$ in the number system with base $$$k$$$ is at the $$$i$$$-th position after sorting.

## Examples
```input
8
2 2
4 2
6 4
33 2
532 13
780011804570805480 3788
366364720306464627 4702032149561577
293940402103595405 2
```
```output
2
2
1
3
1
3789
1
7
```

## Note
In the first test case, for numbers $$$1$$$ and $$$2$$$, their representations are at positions $$$1$$$ and $$$2$$$ respectively.

In the second test case, the sorted array is $$$[1_2 = 1, 10_2 = 2, 100_2 = 4, 11_2 = 3]$$$, and only the representations of numbers $$$1$$$ and $$$2$$$ are at the required positions.

In the third test case, the sorted array is $$$[1_4 = 1, 10_4 = 4, 11_4 = 5, 12_4 = 6, 2_4 = 2, 3_4 = 3]$$$, and only the number $$$1$$$ is at its position.

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

# Problem
It is well known that quick sort works by randomly selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. But Jellyfish thinks that choosing a random element is just a waste of time, so she always chooses the first element to be the pivot. The time her code needs to run can be calculated by the following pseudocode:

Now you want to show her that her code is slow. When the function $$$\mathrm{fun(A)}$$$ is greater than or equal to $$$lim$$$, her code will get $$$\text{Time Limit Exceeded}$$$. You want to know how many distinct permutations $$$P$$$ of $$$[1, 2, \dots, n]$$$ satisfies $$$\mathrm{fun(P)} \geq lim$$$. Because the answer may be large, you will only need to find the answer modulo $$$10^9+7$$$.

## Input Format
The only line of the input contains two integers $$$n$$$ and $$$lim$$$ ($$$1 \leq n \leq 200$$$, $$$1 \leq lim \leq 10^9$$$).

## Output Format
Output the number of different permutations that satisfy the condition modulo $$$10^9+7$$$.

## Examples
```input
4 10
```
```output
8
```
-----
```input
8 32
```
```output
1280
```

## Note
In the first example, $$$P = [1, 4, 2, 3]$$$ satisfies the condition, because: $$$\mathrm{fun([1, 4, 2, 3]) = 4 + fun([4, 2, 3]) = 7 + fun([2, 3]) = 9 + fun([3]) = 10}$$$

Do remember to output the answer modulo $$$10^9+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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Jellyfish always uses OEIS to solve math problems, but now she finds a problem that cannot be solved by OEIS:

Count the number of permutations $$$p$$$ of $$$[1, 2, \dots, n]$$$ such that for all $$$(l, r)$$$ such that $$$l \leq r \leq m_l$$$, the subarray $$$[p_l, p_{l+1}, \dots, p_r]$$$ is not a permutation of $$$[l, l+1, \dots, r]$$$.

Since the answer may be large, you only need to find the answer modulo $$$10^9+7$$$.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 200$$$) — the length of the permutation.

The second line of the input contains $$$n$$$ integers $$$m_1, m_2, \dots, m_n$$$ ($$$0 \leq m_i \leq n$$$).

## Output Format
Output the number of different permutations that satisfy the conditions, modulo $$$10^9+7$$$.

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

## Note
In the first example, $$$[2, 3, 1]$$$ and $$$[3, 1, 2]$$$ satisfies the condition.

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
Given a string $$$x$$$ of length $$$n$$$ and a string $$$s$$$ of length $$$m$$$ ($$$n \cdot m \le 25$$$), consisting of lowercase Latin letters, you can apply any number of operations to the string $$$x$$$.

In one operation, you append the current value of $$$x$$$ to the end of the string $$$x$$$. Note that the value of $$$x$$$ will change after this.

For example, if $$$x =$$$"aba", then after applying operations, $$$x$$$ will change as follows: "aba" $$$\rightarrow$$$ "abaaba" $$$\rightarrow$$$ "abaabaabaaba".

After what minimum number of operations $$$s$$$ will appear in $$$x$$$ as a substring? A substring of a string is defined as a contiguous segment of it.

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

The first line of each test case contains two numbers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 25$$$) — the lengths of strings $$$x$$$ and $$$s$$$, respectively.

The second line of each test case contains the string $$$x$$$ of length $$$n$$$.

The third line of each test case contains the string $$$s$$$ of length $$$m$$$.

## Output Format
For each test case, output a single number — the minimum number of operations after which $$$s$$$ will appear in $$$x$$$ as a substring. If this is not possible, output $$$-1$$$.

## Examples
```input
12
1 5
a
aaaaa
5 5
eforc
force
2 5
ab
ababa
3 5
aba
ababa
4 3
babb
bbb
5 1
aaaaa
a
4 2
aabb
ba
2 8
bk
kbkbkbkb
12 2
fjdgmujlcont
tf
2 2
aa
aa
3 5
abb
babba
1 19
m
mmmmmmmmmmmmmmmmmmm
```
```output
3
1
2
-1
1
0
1
3
1
0
2
5
```

## Note
In the first test case of the example, after $$$2$$$ operations, the string will become "aaaa", and after $$$3$$$ operations, it will become "aaaaaaaa", so the answer is $$$3$$$.

In the second test case of the example, after applying $$$1$$$ operation, the string will become "$$$\text{e}\color{red}{\text{force}}\text{forc}$$$", where the substring is highlighted in red.

In the fourth test case of the example, it can be shown that it is impossible to obtain the desired string as a substring.

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
Kristina has a matrix of size $$$n$$$ by $$$n$$$, filled with lowercase Latin letters. The value of $$$n$$$ is even.

She wants to change some characters so that her matrix becomes a perfect square. A matrix is called a perfect square if it remains unchanged when rotated $$$90^\circ$$$ clockwise once.

Here is an example of rotating a matrix by $$$90^\circ$$$:

In one operation, Kristina can choose any cell and replace its value with the next character in the alphabet. If the character is equal to "z", its value does not change.

Find the minimum number of operations required to make the matrix a perfect square.

For example, if the $$$4$$$ by $$$4$$$ matrix looks like this:

$$$$$$\matrix{ a & b & b & a \cr b & c & \textbf{b} & b \cr b & c & c & b\cr a & b & b & a \cr }$$$$$$

then it is enough to apply $$$1$$$ operation to the letter b, highlighted in bold.

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

Then follows the description of each test case.

The first line of each test case contains a single even integer $$$n$$$ ($$$2 \le n \le 10^3$$$) — the number of rows and columns in the matrix.

Then follows $$$n$$$ lines, each containing exactly $$$n$$$ lowercase Latin letters.

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

## Output Format
For each test case, output a single number on a separate line: the minimum number of operations required for Kristina to obtain a perfect square.

## Examples
```input
5
4
abba
bcbb
bccb
abba
2
ab
ba
6
codefo
rcesco
deforc
escode
forces
codefo
4
baaa
abba
baba
baab
4
bbaa
abba
aaba
abba
```
```output
1
2
181
5
9
```

## Note
The first test case is explained in the problem statement.

Now solve the problem and return the code.