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: 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 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
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 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 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.
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
Nikephoros and Polycarpus play rock-paper-scissors. The loser gets pinched (not too severely!).

Let us remind you the rules of this game. Rock-paper-scissors is played by two players. In each round the players choose one of three items independently from each other. They show the items with their hands: a rock, scissors or paper. The winner is determined by the following rules: the rock beats the scissors, the scissors beat the paper and the paper beats the rock. If the players choose the same item, the round finishes with a draw.

Nikephoros and Polycarpus have played n rounds. In each round the winner gave the loser a friendly pinch and the loser ended up with a fresh and new red spot on his body. If the round finished in a draw, the players did nothing and just played on.

Nikephoros turned out to have worked out the following strategy: before the game began, he chose some sequence of items A = (a1, a2, ..., am), and then he cyclically showed the items from this sequence, starting from the first one. Cyclically means that Nikephoros shows signs in the following order: a1, a2, ..., am, a1, a2, ..., am, a1, ... and so on. Polycarpus had a similar strategy, only he had his own sequence of items B = (b1, b2, ..., bk).

Determine the number of red spots on both players after they've played n rounds of the game. You can consider that when the game began, the boys had no red spots on them.

## Input Format
The first line contains integer n (1 ≤ n ≤ 2·109) — the number of the game's rounds.

The second line contains sequence A as a string of m characters and the third line contains sequence B as a string of k characters (1 ≤ m, k ≤ 1000). The given lines only contain characters "R", "S" and "P". Character "R" stands for the rock, character "S" represents the scissors and "P" represents the paper.

## Output Format
Print two space-separated integers: the numbers of red spots Nikephoros and Polycarpus have.

## Examples
```input
7
RPS
RSPP
```
```output
3 2
```
-----
```input
5
RRRRRRRR
R
```
```output
0 0
```

## Note
In the first sample the game went like this:

- R - R. Draw.
- P - S. Nikephoros loses.
- S - P. Polycarpus loses.
- R - P. Nikephoros loses.
- P - R. Polycarpus loses.
- S - S. Draw.
- R - P. Nikephoros loses.

Thus, in total Nikephoros has 3 losses (and 3 red spots), and Polycarpus only has 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 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
The Trinitarian kingdom has exactly n = 3k cities. All of them are located on the shores of river Trissisipi, which flows through the whole kingdom. Some of the cities are located on one side of the river, and all the rest are on the other side.

Some cities are connected by bridges built between them. Each bridge connects two cities that are located on the opposite sides of the river. Between any two cities exists no more than one bridge.

The recently inaugurated King Tristan the Third is busy distributing his deputies among cities. In total there are k deputies and the king wants to commission each of them to control exactly three cities. However, no deputy can be entrusted to manage the cities, which are connected by a bridge — the deputy can set a too high fee for travelling over the bridge to benefit his pocket, which is bad for the reputation of the king.

Help King Tristan the Third distribute the deputies between the cities, if it is possible.

## Input Format
The first line contains two integers n and m — the number of cities and bridges (3 ≤ n < 105, n = 3k, 0 ≤ m ≤ 105). Next m lines describe the bridges. The i-th line contains two integers ai and bi — the numbers of cities that are connected by the i-th bridge (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ i ≤ m).

It is guaranteed that no bridge connects a city with itself and that any two cities are connected with no more than one bridge.

## Output Format
If distributing the deputies in the required manner is impossible, print in a single line "NO" (without the quotes).

Otherwise, in the first line print "YES" (without the quotes), and in the second line print which deputy should be put in charge of each city. The i-th number should represent the number of the deputy (from 1 to k), who should be in charge of city numbered i-th in the input — overall there should be n numbers.

If there are multiple solutions, print any of them.

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

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
Your working week consists of $$$n$$$ days numbered from $$$1$$$ to $$$n$$$, after day $$$n$$$ goes day $$$1$$$ again. And $$$3$$$ of them are days off. One of the days off is the last day, day $$$n$$$. You have to decide when the other two are.

Choosing days off, you pursue two goals:

- No two days should go one after the other. Note that you can't make day $$$1$$$ a day off because it follows day $$$n$$$.
- Working segments framed by days off should be as dissimilar as possible in duration. More specifically, if the segments are of size $$$l_1$$$, $$$l_2$$$, and $$$l_3$$$ days long, you want to maximize $$$\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)$$$.

Output the maximum value of $$$\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)$$$ that can be obtained.

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

The only line of each test case contains the integer $$$n$$$ ($$$6 \le n \le 10^9$$$).

## Output Format
For each test case, output one integer — the maximum possible obtained value.

## Examples
```input
3
6
10
1033
```
```output
0
1
342
```

## Note
In the image below you can see the example solutions for the first two test cases. Chosen days off are shown in purple. Working segments are underlined in green.

In test case $$$1$$$, the only options for days off are days $$$2$$$, $$$3$$$, and $$$4$$$ (because $$$1$$$ and $$$5$$$ are next to day $$$n$$$). So the only way to place them without selecting neighboring days is to choose days $$$2$$$ and $$$4$$$. Thus, $$$l_1 = l_2 = l_3 = 1$$$, and the answer $$$\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0$$$.

For test case $$$2$$$, one possible way to choose days off is shown. The working segments have the lengths of $$$2$$$, $$$1$$$, and $$$4$$$ days. So the minimum difference is $$$1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|)$$$. It can be shown that there is no way to make it larger.

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
There are $$$n$$$ pieces of tangerine peel, the $$$i$$$-th of them has size $$$a_i$$$. In one step it is possible to divide one piece of size $$$x$$$ into two pieces of positive integer sizes $$$y$$$ and $$$z$$$ so that $$$y + z = x$$$.

You want that for each pair of pieces, their sizes differ strictly less than twice. In other words, there should not be two pieces of size $$$x$$$ and $$$y$$$, such that $$$2x \le y$$$. What is the minimum possible number of steps needed to satisfy the condition?

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

The first line of each test case contains the integer $$$n$$$ ($$$1 \le n \le 100$$$).

Then one line follows, containing $$$n$$$ integers $$$a_1 \le a_2 \le \ldots \le a_n$$$ ($$$1 \le a_i \le 10^7$$$).

## Output Format
For each test case, output a single line containing the minimum number of steps.

## Examples
```input
3
5
1 2 3 4 5
1
1033
5
600 900 1300 2000 2550
```
```output
10
0
4
```

## Note
In the first test case, we initially have a piece of size $$$1$$$, so all final pieces must have size $$$1$$$. The total number of steps is: $$$0 + 1 + 2 + 3 + 4 = 10$$$.

In the second test case, we have just one piece, so we don't need to do anything, and the answer is $$$0$$$ steps.

In the third test case, one of the possible cut options is: $$$600,\ 900,\ (600 | 700),\ (1000 | 1000),\ (1000 | 1000 | 550)$$$. You can see this option in the picture below. The maximum piece has size $$$1000$$$, and it is less than $$$2$$$ times bigger than the minimum piece of size $$$550$$$. $$$4$$$ steps are done. We can show that it is the minimum possible number of steps.

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
For an array of non-negative integers $$$a$$$ of size $$$n$$$, we construct another array $$$d$$$ as follows: $$$d_1 = a_1$$$, $$$d_i = |a_i - a_{i - 1}|$$$ for $$$2 \le i \le n$$$.

Your task is to restore the array $$$a$$$ from a given array $$$d$$$, or to report that there are multiple possible arrays.

## 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 one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the size of the arrays $$$a$$$ and $$$d$$$.

The second line contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ ($$$0 \le d_i \le 100$$$) — the elements of the array $$$d$$$.

It can be shown that there always exists at least one suitable array $$$a$$$ under these constraints.

## Output Format
For each test case, print the elements of the array $$$a$$$, if there is only one possible array $$$a$$$. Otherwise, print $$$-1$$$.

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

## Note
In the second example, there are two suitable arrays: $$$[2, 8, 5]$$$ and $$$[2, 8, 11]$$$.

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

# Problem
Monocarp has a dictionary of $$$n$$$ words, consisting of $$$12$$$ first letters of the Latin alphabet. The words are numbered from $$$1$$$ to $$$n$$$. In every pair of adjacent characters in each word, the characters are different. For every word $$$i$$$, Monocarp also has an integer $$$c_i$$$ denoting how often he uses this word.

Monocarp wants to design a keyboard that would allow him to type some of the words easily. A keyboard can be denoted as a sequence of $$$12$$$ first letters of the Latin alphabet, where each letter from a to l appears exactly once.

A word can be typed with the keyboard easily if, for every pair of adjacent characters in the word, these characters are adjacent in the keyboard as well. The optimality of the keyboard is the sum of $$$c_i$$$ over all words $$$i$$$ that can be typed easily with it.

Help Monocarp to design a keyboard with the maximum possible optimality.

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

Then, $$$n$$$ lines follow. The $$$i$$$-th of them contains an integer $$$c_i$$$ ($$$1 \le c_i \le 10^5$$$) and a string $$$s_i$$$ ($$$2 \le |s_i| \le 2000$$$) denoting the $$$i$$$-th word. Each character of $$$s_i$$$ is one of $$$12$$$ first letters of Latin alphabet, in lowercase. For every $$$j \in [1, |s_i| - 1]$$$, the $$$j$$$-th character of $$$s_i$$$ is different from the $$$(j+1)$$$-th one.

Additional constraint on the input: $$$\sum \limits_{i=1}^{n} |s_i| \le 2000$$$.

## Output Format
Print a sequence of $$$12$$$ first letters of the Latin alphabet, where each letter from a to l appears exactly once, denoting the optimal keyboard. If there are multiple answers, you may print any of them.

## Examples
```input
3
7 abacaba
10 cba
4 db
```
```output
hjkildbacefg
```
-----
```input
1
100 abca
```
```output
abcdefghijkl
```

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
Monocarp has forgotten the password to his mobile phone. The password consists of $$$4$$$ digits from $$$0$$$ to $$$9$$$ (note that it can start with the digit $$$0$$$).

Monocarp remembers that his password had exactly two different digits, and each of these digits appeared exactly two times in the password. Monocarp also remembers some digits which were definitely not used in the password.

You have to calculate the number of different sequences of $$$4$$$ digits that could be the password for Monocarp's mobile phone (i. e. these sequences should meet all constraints on Monocarp's password).

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

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 8$$$) — the number of digits for which Monocarp remembers that they were not used in the password.

The second line contains $$$n$$$ different integers $$$a_1, a_2, \dots a_n$$$ ($$$0 \le a_i \le 9$$$) representing the digits that were not used in the password. Note that the digits $$$a_1, a_2, \dots, a_n$$$ are given in ascending order.

## Output Format
For each testcase, print one integer — the number of different $$$4$$$-digit sequences that meet the constraints.

## Examples
```input
2
8
0 1 2 4 5 6 8 9
1
8
```
```output
6
216
```

## Note
In the first example, all possible passwords are: "3377", "3737", "3773", "7337", "7373", "7733".

Now solve the problem and return the code.