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 permutation $$$a_1,a_2,\ldots,a_n$$$ of integers from $$$0$$$ to $$$n - 1$$$. Your task is to find how many permutations $$$b_1,b_2,\ldots,b_n$$$ are similar to permutation $$$a$$$.

Two permutations $$$a$$$ and $$$b$$$ of size $$$n$$$ are considered similar if for all intervals $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$), the following condition is satisfied: $$$$$$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]),$$$$$$ where the $$$\operatorname{MEX}$$$ of a collection of integers $$$c_1,c_2,\ldots,c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in collection $$$c$$$. For example, $$$\operatorname{MEX}([1,2,3,4,5])=0$$$, and $$$\operatorname{MEX}([0,1,2,4,5])=3$$$.

Since the total number of such permutations can be very large, you will have to print its remainder modulo $$$10^9+7$$$.

In this problem, a permutation of size $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$0$$$ to $$$n-1$$$ in arbitrary order. For example, $$$[1,0,2,4,3]$$$ is a permutation, while $$$[0,1,1]$$$ is not, since $$$1$$$ appears twice in the array. $$$[0,1,3]$$$ is also not a permutation, since $$$n=3$$$ and there is a $$$3$$$ in the array.

## Input Format
Each test contains multiple test cases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The following lines contain the descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the size of permutation $$$a$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt n$$$) — the elements of permutation $$$a$$$.

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

## Output Format
For each test case, print a single integer, the number of permutations similar to permutation $$$a$$$, taken modulo $$$10^9+7$$$.

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

## Note
For the first test case, the only permutations similar to $$$a=[4,0,3,2,1]$$$ are $$$[4,0,3,2,1]$$$ and $$$[4,0,2,3,1]$$$.

For the second and third test cases, the given permutations are only similar to themselves.

For the fourth test case, there are $$$4$$$ permutations similar to $$$a=[1,2,4,0,5,3]$$$:

- $$$[1,2,4,0,5,3]$$$;
- $$$[1,2,5,0,4,3]$$$;
- $$$[1,4,2,0,5,3]$$$;
- $$$[1,5,2,0,4,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 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 are given an integer $$$n$$$ and an array $$$a_1,a_2,\ldots,a_n$$$.

In one operation, you can choose an index $$$i$$$ ($$$1 \le i \lt n$$$) for which $$$a_i \neq a_{i+1}$$$ and delete both $$$a_i$$$ and $$$a_{i+1}$$$ from the array. After deleting $$$a_i$$$ and $$$a_{i+1}$$$, the remaining parts of the array are concatenated.

For example, if $$$a=[1,4,3,3,6,2]$$$, then after performing an operation with $$$i=2$$$, the resulting array will be $$$[1,3,6,2]$$$.

What is the maximum possible length of an array of equal elements obtainable from $$$a$$$ by performing several (perhaps none) of the aforementioned operations?

## Input Format
Each test contains multiple test cases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The following lines contain the descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the length of array $$$a$$$.

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

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10\,000$$$.

## Output Format
For each testcase, print a single integer, the maximum possible length of an array of equal elements obtainable from $$$a$$$ by performing a sequence of operations.

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

## Note
For the first testcase, an optimal sequence of operations would be: $$$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$$$.

For the second testcase, all elements in the array are already equal.

For the third testcase, the only possible sequence of operations is: $$$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$$$. Note that, according to the statement, the elements deleted at each step must be different.

For the fourth testcase, the optimal sequence of operations is: $$$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$$$.

For the fifth testcase, one possible reachable array of two equal elements is $$$[4,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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ positive integers.

You are allowed to perform this operation any number of times (possibly, zero):

- choose an index $$$i$$$ ($$$2 \le i \le n$$$), and change $$$a_i$$$ to $$$a_i - a_{i-1}$$$.

Is it possible to make $$$a_i=0$$$ for all $$$2\le i\le n$$$?

## 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 contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

## Output Format
For each test case, print "YES" (without quotes), if it is possible to change $$$a_i$$$ to $$$0$$$ for all $$$2 \le i \le n$$$, and "NO" (without quotes) otherwise.

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

## Examples
```input
4
2
5 10
3
1 2 3
4
1 1 1 1
9
9 9 8 2 4 4 3 5 3
```
```output
YES
YES
YES
NO
```

## Note
In the first test case, the initial array is $$$[5,10]$$$. You can perform $$$2$$$ operations to reach the goal:

1. Choose $$$i=2$$$, and the array becomes $$$[5,5]$$$.
2. Choose $$$i=2$$$, and the array becomes $$$[5,0]$$$.

In the second test case, the initial array is $$$[1,2,3]$$$. You can perform $$$4$$$ operations to reach the goal:

1. Choose $$$i=3$$$, and the array becomes $$$[1,2,1]$$$.
2. Choose $$$i=2$$$, and the array becomes $$$[1,1,1]$$$.
3. Choose $$$i=3$$$, and the array becomes $$$[1,1,0]$$$.
4. Choose $$$i=2$$$, and the array becomes $$$[1,0,0]$$$.

In the third test case, you can choose indices in the order $$$4$$$, $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given three integers $$$n$$$, $$$l$$$, and $$$r$$$. You need to construct an array $$$a_1,a_2,\dots,a_n$$$ ($$$l\le a_i\le r$$$) such that $$$\gcd(i,a_i)$$$ are all distinct or report there's no solution.

Here $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

## 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. The description of the test cases follows.

The first line contains three integers $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \le n \le 10^5$$$, $$$1\le l\le r\le 10^9$$$).

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

## Output Format
For each test case, if there is no solution, print "NO" (without quotes). You can print letters in any case (upper or lower).

Otherwise, print "YES" (without quotes). In the next line, print $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ — the array you construct.

If there are multiple solutions, you may output any.

## Examples
```input
4
5 1 5
9 1000 2000
10 30 35
1 1000000000 1000000000
```
```output
YES
1 2 3 4 5
YES
1145 1926 1440 1220 1230 1350 1001 1000 1233
NO
YES
1000000000
```

## Note
In the first test case, $$$\gcd(1,a_1),\gcd(2,a_2),\ldots,\gcd(5,a_5)$$$ are equal to $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, respectively.

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

# Problem
Rhodoks has a tree with $$$n$$$ vertices, but he doesn't remember its structure. The vertices are indexed from $$$1$$$ to $$$n$$$.

A segment $$$[l,r]$$$ ($$$1 \leq l \leq r \leq n$$$) is good if the vertices with indices $$$l$$$, $$$l + 1$$$, ..., $$$r$$$ form a connected component in Rhodoks' tree. Otherwise, it is bad.

For example, if the tree is the one in the picture, then only the segment $$$[3,4]$$$ is bad while all the other segments are good.

For each of the $$$\frac{n(n+1)}{2}$$$ segments, Rhodoks remembers whether it is good or bad. Can you help him recover the tree? If there are multiple solutions, print any.

It is guaranteed that the there is at least one tree satisfying Rhodoks' description.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the number of vertices in the tree.

Then $$$n$$$ lines follow. The $$$i$$$-th of these lines contains a string $$$good_i$$$ of length $$$n+1-i$$$ consisting of 0 and 1. If the segment $$$[i,i+j-1]$$$ is good then the $$$j$$$-th character of $$$good_i$$$ is 1, otherwise $$$j$$$-th character of $$$good_i$$$ is 0.

It is guaranteed that the there is at least one tree consistent with the given data.

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

## Output Format
For each test case, print $$$n-1$$$ lines describing the tree you recover.

The $$$i$$$-th line should contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i,v_i \leq n$$$), denoting an edge between vertices $$$u_i$$$ and $$$v_i$$$.

If there are multiple solutions, print any.

## Examples
```input
3
4
1111
111
10
1
6
111111
11111
1111
111
11
1
12
100100000001
11100000001
1000000000
100000000
10010001
1110000
100000
10000
1001
111
10
1
```
```output
1 2
2 3
2 4
1 2
2 3
3 4
4 5
5 6
2 3
6 7
10 11
2 4
6 8
10 12
1 4
5 8
9 12
5 12
2 12
```

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

In the second test case, one possible tree is as follows:

In the third test case, one possible tree is as follows:

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 are given two arrays of integers $$$a_1,a_2,\dots,a_n$$$ and $$$b_1,b_2,\dots,b_m$$$.

Alice and Bob are going to play a game. Alice moves first and they take turns making a move.

They play on a grid of size $$$n \times m$$$ (a grid with $$$n$$$ rows and $$$m$$$ columns). Initially, there is a rook positioned on the first row and first column of the grid.

During her/his move, a player can do one of the following two operations:

1. Move the rook to a different cell on the same row or the same column of the current cell. A player cannot move the rook to a cell that has been visited $$$1000$$$ times before (i.e., the rook can stay in a certain cell at most $$$1000$$$ times during the entire game). Note that the starting cell is considered to be visited once at the beginning of the game.
2. End the game immediately with a score of $$$a_r+b_c$$$, where $$$(r, c)$$$ is the current cell (i.e., the rook is on the $$$r$$$-th row and $$$c$$$-th column).

Bob wants to maximize the score while Alice wants to minimize it. If they both play this game optimally, what is the final score of the game?

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 2 \cdot 10^5$$$) — the length of the arrays $$$a$$$ and $$$b$$$ (which coincide with the number of rows and columns of the grid).

The second line contains the $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^8$$$).

The third line contains the $$$m$$$ integers $$$b_1, b_2,\dots, b_n$$$ ($$$1 \leq b_i \leq 5 \cdot 10^8$$$).

## Output Format
Print a single line containing the final score of the game.

## Examples
```input
2 1
3 2
2
```
```output
4
```
-----
```input
4 5
235499701 451218171 355604420 132973458
365049318 264083156 491406845 62875547 175951751
```
```output
531556171
```

## Note
In the first test case, Alice moves the rook to $$$(2, 1)$$$ and Bob moves the rook to $$$(1, 1)$$$. This process will repeat for $$$999$$$ times until finally, after Alice moves the rook, Bob cannot move it back to $$$(1, 1)$$$ because it has been visited $$$1000$$$ times before. So the final score of the game is $$$a_2+b_1=4$$$.

In the second test case, the final score of the game is $$$a_3+b_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 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 have an image file of size $$$2 \times 2$$$, consisting of $$$4$$$ pixels. Each pixel can have one of $$$26$$$ different colors, denoted by lowercase Latin letters.

You want to recolor some of the pixels of the image so that all $$$4$$$ pixels have the same color. In one move, you can choose no more than two pixels of the same color and paint them into some other color (if you choose two pixels, both should be painted into the same color).

What is the minimum number of moves you have to make in order to fulfill your goal?

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

Each test case consists of two lines. Each of these lines contains two lowercase letters of Latin alphabet without any separators, denoting a row of pixels in the image.

## Output Format
For each test case, print one integer — the minimum number of moves you have to make so that all $$$4$$$ pixels of the image have the same color.

## Examples
```input
5
rb
br
cc
wb
aa
aa
ab
cd
yy
xx
```
```output
1
2
0
3
1
```

## Note
Let's analyze the test cases of the example.

In the first test case, you can paint the bottom left pixel and the top right pixel (which share the same color) into the color r, so all pixels have this color.

In the second test case, two moves are enough:

- paint both top pixels, which have the same color c, into the color b;
- paint the bottom left pixel into the color b.

In the third test case, all pixels already have the same color.

In the fourth test case, you may leave any of the pixels unchanged, and paint all three other pixels into the color of that pixel in three moves.

In the fifth test case, you can paint both top pixels into the color x.

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
The robot is placed in the top left corner of a grid, consisting of $$$n$$$ rows and $$$m$$$ columns, in a cell $$$(1, 1)$$$.

In one step, it can move into a cell, adjacent by a side to the current one:

- $$$(x, y) \rightarrow (x, y + 1)$$$;
- $$$(x, y) \rightarrow (x + 1, y)$$$;
- $$$(x, y) \rightarrow (x, y - 1)$$$;
- $$$(x, y) \rightarrow (x - 1, y)$$$.

The robot can't move outside the grid.

The cell $$$(s_x, s_y)$$$ contains a deadly laser. If the robot comes into some cell that has distance less than or equal to $$$d$$$ to the laser, it gets evaporated. The distance between two cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is $$$|x_1 - x_2| + |y_1 - y_2|$$$.

Print the smallest number of steps that the robot can take to reach the cell $$$(n, m)$$$ without getting evaporated or moving outside the grid. If it's not possible to reach the cell $$$(n, m)$$$, print -1.

The laser is neither in the starting cell, nor in the ending cell. The starting cell always has distance greater than $$$d$$$ to the laser.

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

The only line of each testcase contains five integers $$$n, m, s_x, s_y, d$$$ ($$$2 \le n, m \le 1000$$$; $$$1 \le s_x \le n$$$; $$$1 \le s_y \le m$$$; $$$0 \le d \le n + m$$$) — the size of the grid, the cell that contains the laser and the evaporating distance of the laser.

The laser is neither in the starting cell, nor in the ending cell ($$$(s_x, s_y) \neq (1, 1)$$$ and $$$(s_x, s_y) \neq (n, m)$$$). The starting cell $$$(1, 1)$$$ always has distance greater than $$$d$$$ to the laser ($$$|s_x - 1| + |s_y - 1| > d$$$).

## Output Format
For each testcase, print a single integer. If it's possible to reach the cell $$$(n, m)$$$ from $$$(1, 1)$$$ without getting evaporated or moving outside the grid, then print the smallest amount of steps it can take the robot to reach it. Otherwise, print -1.

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

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 are given a string $$$s$$$, consisting of lowercase Latin letters.

You are asked $$$q$$$ queries about it: given another string $$$t$$$, consisting of lowercase Latin letters, perform the following steps:

1. concatenate $$$s$$$ and $$$t$$$;
2. calculate the prefix function of the resulting string $$$s+t$$$;
3. print the values of the prefix function on positions $$$|s|+1, |s|+2, \dots, |s|+|t|$$$ ($$$|s|$$$ and $$$|t|$$$ denote the lengths of strings $$$s$$$ and $$$t$$$, respectively);
4. revert the string back to $$$s$$$.

The prefix function of a string $$$a$$$ is a sequence $$$p_1, p_2, \dots, p_{|a|}$$$, where $$$p_i$$$ is the maximum value of $$$k$$$ such that $$$k < i$$$ and $$$a[1..k]=a[i-k+1..i]$$$ ($$$a[l..r]$$$ denotes a contiguous substring of a string $$$a$$$ from a position $$$l$$$ to a position $$$r$$$, inclusive). In other words, it's the longest proper prefix of the string $$$a[1..i]$$$ that is equal to its suffix of the same length.

## Input Format
The first line contains a non-empty string $$$s$$$ ($$$1 \le |s| \le 10^6$$$), consisting of lowercase Latin letters.

The second line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains a query: a non-empty string $$$t$$$ ($$$1 \le |t| \le 10$$$), consisting of lowercase Latin letters.

## Output Format
For each query, print the values of the prefix function of a string $$$s+t$$$ on positions $$$|s|+1, |s|+2, \dots, |s|+|t|$$$.

## Examples
```input
aba
6
caba
aba
bababa
aaaa
b
forces
```
```output
0 1 2 3 
1 2 3 
2 3 4 5 6 7 
1 1 1 1 
2 
0 0 0 0 0 0
```
-----
```input
aacba
4
aaca
cbbb
aab
ccaca
```
```output
2 2 3 1 
0 0 0 0 
2 2 0 
0 0 1 0 1
```

Now solve the problem and return the code.