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 an array $$$a$$$ with $$$n$$$ integers. You can perform the following operation at most $$$k$$$ times:

- Choose two indices $$$i$$$ and $$$j$$$, in which $$$i \,\bmod\, k = j \,\bmod\, k$$$ ($$$1 \le i < j \le n$$$).
- Swap $$$a_i$$$ and $$$a_j$$$.

After performing all operations, you have to select $$$k$$$ consecutive elements, and the sum of the $$$k$$$ elements becomes your score. Find the maximum score you can get.

Here $$$x \bmod y$$$ denotes the remainder from dividing $$$x$$$ by $$$y$$$.

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

Each test case consists of two lines.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the length of the array and the number in the statement above.

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

## Output Format
For each test case, print the maximum score you can get, one per line.

## Examples
```input
5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997
```
```output
11
7
15
10
2999999997
```

## Note
In the first test case, we can get a score of $$$11$$$ if we select $$$a_1, a_2$$$ without performing any operations.

In the third test case, we can get a score of $$$15$$$ if we first swap $$$a_1$$$ with $$$a_4$$$ and then select $$$a_3, a_4, a_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: 256.0 MB

# Problem
There is a badminton championship in which $$$n$$$ players take part. The players are numbered from $$$1$$$ to $$$n$$$.

The championship proceeds as follows: player $$$1$$$ and player $$$2$$$ play a game, then the winner and player $$$3$$$ play a game, and then the winner and player $$$4$$$ play a game, and so on. So, $$$n-1$$$ games are played, and the winner of the last game becomes the champion. There are no draws in the games.

You want to find out the result of championship. Currently, you only know the following information:

- Each player has either won $$$x$$$ games or $$$y$$$ games in the championship.

Given $$$n$$$, $$$x$$$, and $$$y$$$, find out if there is a result that matches this information.

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

The only line of each test case contains three integers $$$n$$$, $$$x$$$, $$$y$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le x, y < n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
Print the answer for each test case, one per line. If there is no result that matches the given information about $$$n$$$, $$$x$$$, $$$y$$$, print $$$-1$$$. Otherwise, print $$$n-1$$$ space separated integers, where the $$$i$$$-th integer is the player number of the winner of the $$$i$$$-th game.

If there are multiple valid results, print any.

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

## Note
In the first test case, player $$$1$$$ and player $$$4$$$ won $$$x$$$ times, player $$$2$$$ and player $$$3$$$ won $$$y$$$ times.

In the second, third, and fifth test cases, no valid result exists.

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 array $$$a$$$ with $$$n$$$ non-negative integers. You can apply the following operation on it.

- Choose two indices $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$).
- If $$$a_l + a_r$$$ is odd, do $$$a_r := a_l$$$. If $$$a_l + a_r$$$ is even, do $$$a_l := a_r$$$.

Find any sequence of at most $$$n$$$ operations that makes $$$a$$$ non-decreasing. It can be proven that it is always possible. Note that you do not have to minimize the number of operations.

An array $$$a_1, a_2, \ldots, a_n$$$ is non-decreasing if and only if $$$a_1 \le a_2 \le \ldots \le a_n$$$.

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

Each test case consists of two lines. The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.

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

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, print one integer $$$m$$$ ($$$0 \le m \le n$$$), the number of operations, in the first line.

Then print $$$m$$$ lines. Each line must contain two integers $$$l_i, r_i$$$, which are the indices you chose in the $$$i$$$-th operation ($$$1 \le l_i < r_i \le n$$$).

If there are multiple solutions, print any of them.

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

## Note
In the second test case, $$$a$$$ changes like this:

- Select indices $$$3$$$ and $$$4$$$. $$$a_3 + a_4 = 3$$$ is odd, so do $$$a_4 := a_3$$$. $$$a = [1, 1000000000, 3, 3, 5]$$$ now.
- Select indices $$$1$$$ and $$$2$$$. $$$a_1 + a_2 = 1000000001$$$ is odd, so do $$$a_2 := a_1$$$. $$$a = [1, 1, 3, 3, 5]$$$ now, and it is non-decreasing.

In the first and third test cases, $$$a$$$ is already non-decreasing.

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

# Problem
This is the easy version of the problem. In this version, $$$n \le 3000$$$, $$$x \ge y$$$ holds. You can make hacks only if both versions of the problem are solved.

You are given two binary strings $$$a$$$ and $$$b$$$, both of length $$$n$$$. You can do the following operation any number of times (possibly zero).

- Select two indices $$$l$$$ and $$$r$$$ ($$$l < r$$$).
- Change $$$a_l$$$ to $$$(1 - a_l)$$$, and $$$a_r$$$ to $$$(1 - a_r)$$$.
- If $$$l + 1 = r$$$, the cost of the operation is $$$x$$$. Otherwise, the cost is $$$y$$$.

You have to find the minimum cost needed to make $$$a$$$ equal to $$$b$$$ or say there is no way to do so.

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

Each test case consists of three lines. The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$5 \le n \le 3000$$$, $$$1 \le y \le x \le 10^9$$$) — the length of the strings, and the costs per operation.

The second line of each test case contains the string $$$a$$$ of length $$$n$$$. The string only consists of digits $$$0$$$ and $$$1$$$.

The third line of each test case contains the string $$$b$$$ of length $$$n$$$. The string only consists of digits $$$0$$$ and $$$1$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3000$$$.

## Output Format
For each test case, if there is no way to make $$$a$$$ equal to $$$b$$$, print $$$-1$$$. Otherwise, print the minimum cost needed to make $$$a$$$ equal to $$$b$$$.

## Examples
```input
4
5 8 7
01001
00101
5 7 2
01000
11011
7 8 3
0111001
0100001
5 10 1
01100
01100
```
```output
8
-1
6
0
```

## Note
In the first test case, selecting indices $$$2$$$ and $$$3$$$ costs $$$8$$$, which is the minimum possible cost.

In the second test case, we cannot make $$$a$$$ equal to $$$b$$$ using any number of operations.

In the third test case, we can perform the following operations:

- Select indices $$$3$$$ and $$$6$$$. It costs $$$3$$$, and $$$a$$$ is 0101011 now.
- Select indices $$$4$$$ and $$$6$$$. It costs $$$3$$$, and $$$a$$$ is 0100001 now.

The total cost is $$$6$$$.

In the fourth test case, we don't have to perform any operations.

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
There is a conveyor with $$$120$$$ rows and $$$120$$$ columns. Each row and column is numbered from $$$0$$$ to $$$119$$$, and the cell in $$$i$$$-th row and $$$j$$$-th column is denoted as $$$(i, j)$$$. The top leftmost cell is $$$(0, 0)$$$. Each cell has a belt, and all belts are initially facing to the right.

Initially, a slime ball is on the belt of $$$(0, 0)$$$, and other belts are empty. Every second, the state of the conveyor changes as follows:

- All slime balls on the conveyor move one cell in the direction of the belt at the same time. If there is no cell in the moved position, the slime gets out of the conveyor, and if two slime balls move to the same cell, they merge into one.
- All belts with slime ball in the previous second change direction at the same time: belts facing to the right become facing to the down, and vice versa.
- A new slime ball is placed on cell $$$(0, 0)$$$.

There are $$$q$$$ queries, each being three integers $$$t$$$, $$$x$$$, and $$$y$$$. You have to find out if there is a slime at the cell $$$(x, y)$$$ after $$$t$$$ seconds from the start. Can you do it?

## Input Format
The first line contains one integer $$$q$$$ ($$$1 \le q \le 10^4$$$) — the number of queries.

The only line of each query contains three integers $$$t$$$, $$$x$$$, and $$$y$$$ ($$$0 \le t \le 10^{18}$$$, $$$0 \le x, y < 120$$$).

## Output Format
Print the answer for each test case, one per line. If there is a slime ball in the cell $$$(x, y)$$$ after $$$t$$$ seconds from the initial state, print "YES". Otherwise, print "NO".

## Examples
```input
6
1 1 0
5 1 3
0 0 0
2 4 5
2 0 2
1547748756 100 111
```
```output
NO
YES
YES
NO
YES
YES
```

## Note
The state of conveyor with $$$t = 0$$$. Red arrow represents the direction of each belt, and blue figure represents slime.

The state of conveyor with $$$t = 1$$$.

The state of conveyor with $$$t = 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 two arrays $$$a$$$ and $$$b$$$ of $$$n$$$ elements, each element is either $$$0$$$ or $$$1$$$.

You can make operations of $$$2$$$ kinds.

- Pick an index $$$i$$$ and change $$$a_i$$$ to $$$1-a_i$$$.
- Rearrange the array $$$a$$$ however you want.

Find the minimum number of operations required to make $$$a$$$ equal to $$$b$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of the arrays $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i$$$ is $$$0$$$ or $$$1$$$), representing the array $$$a$$$.

The third line of each test case contains $$$n$$$ space-separated integers $$$b_1,b_2,\ldots,b_n$$$ ($$$b_i$$$ is $$$0$$$ or $$$1$$$), representing the array $$$b$$$.

## Output Format
For each test case, print the minimum number of operations required to make $$$a$$$ equal to $$$b$$$.

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

## Note
In the first case, we need only one operation: change $$$a_1$$$ to $$$1-a_i$$$. Now $$$a = [0, 0]$$$ which is equal to $$$b$$$.

In the second case, the optimal way is to rearrange $$$a$$$ to get the array $$$[0, 1, 11$$$. Now $$$a = [0, 0, 1]$$$ which is equal to $$$b$$$.

In the second case, one of optimal ways would be to first change $$$a_3$$$ to $$$1 - a_3$$$, then rearrange $$$a$$$.

In the third case, no operation is needed.

In the fourth case, the optimal way is to rearrange $$$a$$$ to get the array $$$[0, 1, 1, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer array $$$a$$$ of length $$$n$$$.

Does there exist an array $$$b$$$ consisting of $$$n+1$$$ positive integers such that $$$a_i=\gcd (b_i,b_{i+1})$$$ for all $$$i$$$ ($$$1 \leq i \leq n$$$)?

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

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ representing the array $$$a$$$ ($$$1 \leq a_i \leq 10^4$$$).

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

## Output Format
For each test case, output "YES" if such $$$b$$$ exists, otherwise output "NO". You can print each letter in any case (upper or lower).

## Examples
```input
4
1
343
2
4 2
3
4 2 4
4
1 1 1 1
```
```output
YES
YES
NO
YES
```

## Note
In the first test case, we can take $$$b=[343,343]$$$.

In the second test case, one possibility for $$$b$$$ is $$$b=[12,8,6]$$$.

In the third test case, it can be proved that there does not exist any array $$$b$$$ that fulfills all the conditions.

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 is the easy version of this problem. In this version, we do not have queries. Note that we have multiple test cases in this version. You can make hacks only if both versions of the problem are solved.

An array $$$b$$$ of length $$$m$$$ is good if for all $$$i$$$ the $$$i$$$-th element is greater than or equal to $$$i$$$. In other words, $$$b$$$ is good if and only if $$$b_i \geq i$$$ for all $$$i$$$ ($$$1 \leq i \leq m$$$).

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers. Find the number of pairs of indices $$$(l, r)$$$, where $$$1 \le l \le r \le n$$$, such that the array $$$[a_l, a_{l+1}, \ldots, a_r]$$$ is good.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the array $$$a$$$.

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

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

## Output Format
For each test case, print the number of suitable pairs of indices.

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

## Note
In the first test case, all subarrays of $$$a$$$ are good, so all pairs are suitable.

In the second test case, the pairs $$$(1, 1)$$$, $$$(2, 2)$$$, and $$$(3, 3)$$$ are suitable. For example, when $$$(l, r) = (1, 2)$$$, the array $$$b=[1,1]$$$ is not good because $$$b_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: 2.0 seconds
Memory limit: 1024.0 MB

# Problem
You're given an array consisting of $$$n$$$ integers. You have to perform $$$n$$$ turns.

Initially your score is $$$0$$$.

On the $$$i$$$-th turn, you are allowed to leave the array as it is or swap any one pair of $$$2$$$ adjacent elements in the array and change exactly one of them to $$$0$$$(and leave the value of other element unchanged) after swapping. In either case(whether you swap or not), after this you add $$$a_i$$$ to your score.

What's the maximum possible score you can get?

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 500$$$).

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

## Output Format
Print a single integer — the maximum possible score.

## Examples
```input
2
3 1
```
```output
6
```
-----
```input
5
7 3 9 6 12
```
```output
52
```

## Note
In the first example, to get the maximum score we do as follows. Do nothing on the first turn, add $$$3$$$ to the score. Swap the first and the second elements and turn $$$1$$$ to $$$0$$$ on the second turn, and add $$$3$$$ to the score. The final score is $$$6$$$.

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
There's a chessboard of size $$$n \times n$$$. $$$m$$$ rooks are placed on it in such a way that:

- no two rooks occupy the same cell;
- no two rooks attack each other.

A rook attacks all cells that are in its row or column.

Is it possible to move exactly one rook (you can choose which one to move) into a different cell so that no two rooks still attack each other? A rook can move into any cell in its row or column if no other rook stands on its path.

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

The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 8$$$) — the size of the chessboard and the number of the rooks.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) — the position of the $$$i$$$-th rook: $$$x_i$$$ is the row and $$$y_i$$$ is the column.

No two rooks occupy the same cell. No two rooks attack each other.

## Output Format
For each testcase, print "YES" if it's possible to move exactly one rook into a different cell so that no two rooks still attack each other. Otherwise, print "NO".

## Examples
```input
2
2 2
1 2
2 1
3 1
2 2
```
```output
NO
YES
```

## Note
In the first testcase, the rooks are in the opposite corners of a $$$2 \times 2$$$ board. Each of them has a move into a neighbouring corner, but moving there means getting attacked by another rook.

In the second testcase, there's a single rook in a middle of a $$$3 \times 3$$$ board. It has $$$4$$$ valid moves, and every move is fine because there's no other rook to attack it.

Now solve the problem and return the code.