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

# Problem
Polycarp has a poor memory. Each day he can remember no more than $$$3$$$ of different letters.

Polycarp wants to write a non-empty string of $$$s$$$ consisting of lowercase Latin letters, taking minimum number of days. In how many days will he be able to do it?

Polycarp initially has an empty string and can only add characters to the end of that string.

For example, if Polycarp wants to write the string lollipops, he will do it in $$$2$$$ days:

- on the first day Polycarp will memorize the letters l, o, i and write lolli;
- On the second day Polycarp will remember the letters p, o, s, add pops to the resulting line and get the line lollipops.

If Polycarp wants to write the string stringology, he will do it in $$$4$$$ days:

- in the first day will be written part str;
- on day two will be written part ing;
- on the third day, part of olog will be written;
- on the fourth day, part of y will be written.

For a given string $$$s$$$, print the minimum number of days it will take Polycarp to write it.

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

Each test case consists of a non-empty string $$$s$$$ consisting of lowercase Latin letters (the length of the string $$$s$$$ does not exceed $$$2 \cdot 10^5$$$) — the string Polycarp wants to construct.

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

## Output Format
For each test case, print a single number — minimum number of days it will take Polycarp to write the string $$$s$$$ from memory.

## Examples
```input
6
lollipops
stringology
abracadabra
codeforces
test
f
```
```output
2
4
3
4
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 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
This is an easy version of the problem. The only difference between an easy and a hard version is in the number of queries.

Polycarp grew a tree from $$$n$$$ vertices. We remind you that a tree of $$$n$$$ vertices is an undirected connected graph of $$$n$$$ vertices and $$$n-1$$$ edges that does not contain cycles.

He calls a set of vertices passable if there is such a path in the tree that passes through each vertex of this set without passing through any edge twice. The path can visit other vertices (not from this set).

In other words, a set of vertices is called passable if there is a simple path that passes through all the vertices of this set (and possibly some other).

For example, for a tree below sets $$$\{3, 2, 5\}$$$, $$$\{1, 5, 4\}$$$, $$$\{1, 4\}$$$ are passable, and $$$\{1, 3, 5\}$$$, $$$\{1, 2, 3, 4, 5\}$$$ are not.

Polycarp asks you to answer $$$q$$$ queries. Each query is a set of vertices. For each query, you need to determine whether the corresponding set of vertices is passable.

## Input Format
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of vertices.

Following $$$n - 1$$$ lines a description of the tree..

Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — indices of vertices connected by an edge.

Following line contains single integer $$$q$$$ ($$$1 \le q \le 5$$$) — number of queries.

The following $$$2 \cdot q$$$ lines contain descriptions of sets.

The first line of the description contains an integer $$$k$$$ ($$$1 \le k \le n$$$) — the size of the set.

The second line of the description contains $$$k$$$ of distinct integers $$$p_1, p_2, \dots, p_k$$$ ($$$1 \le p_i \le n$$$) — indices of the vertices of the set.

It is guaranteed that the sum of $$$k$$$ values for all queries does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Output $$$q$$$ lines, each of which contains the answer to the corresponding query. As an answer, output "YES" if the set is passable, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
5
1 2
2 3
2 4
4 5
5
3
3 2 5
5
1 2 3 4 5
2
1 4
3
1 3 5
3
1 5 4
```
```output
YES
NO
YES
NO
YES
```
-----
```input
5
1 2
3 2
2 4
5 2
4
2
3 1
3
3 4 5
3
2 3 5
1
1
```
```output
YES
NO
YES
YES
```

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: 4.0 seconds
Memory limit: 64.0 MB

# Problem
This is the easy version of the problem. The only difference between the versions is the constraints on $$$n$$$, $$$k$$$, $$$a_i$$$, and the sum of $$$n$$$ over all test cases. You can make hacks only if both versions of the problem are solved.

Note the unusual memory limit.

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, and an integer $$$k$$$.

The cost of an array of integers $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$ is $$$$$$\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).$$$$$$

Here, $$$\lfloor \frac{x}{y} \rfloor$$$ denotes the integer part of the division of $$$x$$$ by $$$y$$$. Find the minimum cost of an array $$$p$$$ such that $$$1 \le p_i \le k$$$ for all $$$1 \le i \le n$$$.

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

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

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

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

## Output Format
For each test case, print a single integer — the minimum possible cost of an array $$$p$$$ satisfying the condition above.

## Examples
```input
7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3
```
```output
2
0
13
1
4
7
0
```

## Note
In the first test case, the optimal array is $$$p = [1, 1, 1, 2, 2]$$$. The resulting array of values of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ is $$$[4, 5, 6, 4, 5]$$$. The cost of $$$p$$$ is $$$\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2$$$. We can show that there is no array (satisfying the condition from the statement) with a smaller cost.

In the second test case, one of the optimal arrays is $$$p = [12, 12, 12, 12, 12]$$$, which results in all $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ being $$$0$$$.

In the third test case, the only possible array is $$$p = [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 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
How to make a cake you'll never eat.

Ingredients.

- 2 carrots
- 0 calories
- 100 g chocolate spread
- 1 pack of flour
- 1 egg

Method.

1. Put calories into the mixing bowl.
2. Take carrots from refrigerator.
3. Chop carrots.
4. Take chocolate spread from refrigerator.
5. Put chocolate spread into the mixing bowl.
6. Combine pack of flour into the mixing bowl.
7. Fold chocolate spread into the mixing bowl.
8. Add chocolate spread into the mixing bowl.
9. Put pack of flour into the mixing bowl.
10. Add egg into the mixing bowl.
11. Fold pack of flour into the mixing bowl.
12. Chop carrots until choped.
13. Pour contents of the mixing bowl into the baking dish.

Serves 1.

## Input Format
The only line of input contains a sequence of integers a0, a1, ... (1 ≤ a0 ≤ 100, 0 ≤ ai ≤ 1000 for i ≥ 1).

## Output Format
Output a single integer.

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

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

# Problem
qd ucyhf yi q fhycu dkcruh mxeiu huluhiu yi q tyvvuhudj fhycu dkcruh. oekh jqia yi je vydt jxu djx ucyhf.

## Input Format
jxu ydfkj sediyiji ev q iydwbu ydjuwuh d (1 ≤ d ≤ 11184) — jxu edu-rqiut ydtun ev jxu ucyhf je vydt.

## Output Format
ekjfkj q iydwbu dkcruh.

## Examples
```input
1
```
```output
13
```

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