apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Joi has an array $$$a$$$ of $$$n$$$ positive integers. Koxia wants you to determine whether there exists a positive integer $$$x > 0$$$ such that $$$\gcd(a_i+x,a_j+x)=1$$$ for all $$$1 \leq i < j \leq n$$$.

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

## Input Format
Each test 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 test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq {10}^{18}$$$).

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

## Output Format
For each test case, output "YES" (without quotes) if there exists a positive integer $$$x$$$ such that $$$\gcd(a_i+x,a_j+x)=1$$$ for all $$$1 \leq i < j \leq n$$$, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Examples
```input
2
3
5 7 10
3
3 3 4
```
```output
YES
NO
```

## Note
In the first test case, we can set $$$x = 4$$$. This is valid because:

- When $$$i=1$$$ and $$$j=2$$$, $$$\gcd(a_i+x,a_j+x)=\gcd(5+4,7+4)=\gcd(9,11)=1$$$.
- When $$$i=1$$$ and $$$j=3$$$, $$$\gcd(a_i+x,a_j+x)=\gcd(5+4,10+4)=\gcd(9,14)=1$$$.
- When $$$i=2$$$ and $$$j=3$$$, $$$\gcd(a_i+x,a_j+x)=\gcd(7+4,10+4)=\gcd(11,14)=1$$$.

In the second test case, any choice of $$$x$$$ makes $$$\gcd(a_1 + x, a_2 + x) = \gcd(3+x,3+x)=3+x$$$. Therefore, no such $$$x$$$ 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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Chiyuu has a bracket sequence$$$^\dagger$$$ $$$s$$$ of length $$$n$$$. Let $$$k$$$ be the minimum number of characters that Chiyuu has to remove from $$$s$$$ to make $$$s$$$ balanced$$$^\ddagger$$$.

Now, Koxia wants you to count the number of ways to remove $$$k$$$ characters from $$$s$$$ so that $$$s$$$ becomes balanced, modulo $$$998\,244\,353$$$.

Note that two ways of removing characters are considered distinct if and only if the set of indices removed is different.

$$$^\dagger$$$ A bracket sequence is a string containing only the characters "(" and ")".

$$$^\ddagger$$$ A bracket sequence is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), (()(())) and the empty string are balanced, while )(, ((), and (()))( are not.

## Input Format
The first line of input contains a string $$$s$$$ ($$$1 \leq |s| \leq 5 \cdot {10}^5$$$) — the bracket sequence.

It is guaranteed that $$$s$$$ only contains the characters "(" and ")".

## Output Format
Output a single integer — the number of ways to remove $$$k$$$ characters from $$$s$$$ so that $$$s$$$ becomes balanced, modulo $$$998\,244\,353$$$.

## Examples
```input
())(()
```
```output
4
```
-----
```input
(
```
```output
1
```

## Note
In the first test case, it can be proved that the minimum number of characters that Chiyuu has to remove is $$$2$$$. There are $$$4$$$ ways to remove $$$2$$$ characters to make $$$s$$$ balanced as follows. Deleted characters are noted as red.

- $$$\texttt{(} \color{Red}{\texttt{)}} \texttt{)} \color{Red}{\texttt{(}} \texttt{(} \texttt{)}$$$,
- $$$\texttt{(} \texttt{)} \color{Red}{\texttt{)}} \color{Red}{\texttt{(}} \texttt{(} \texttt{)}$$$,
- $$$\texttt{(} \color{Red}{\texttt{)}} \texttt{)} \texttt{(} \color{Red}{\texttt{(}} \texttt{)}$$$,
- $$$\texttt{(} \texttt{)} \color{Red}{\texttt{)}} \texttt{(} \color{Red}{\texttt{(}} \texttt{)}$$$.

In the second test case, the only way to make $$$s$$$ balanced is by deleting the only character to get an empty bracket sequence, which is considered balanced.

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
AquaMoon has a string $$$a$$$ consisting of only $$$0$$$ and $$$1$$$. She wants to add $$$+$$$ and $$$-$$$ between all pairs of consecutive positions to make the absolute value of the resulting expression as small as possible. Can you help her?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\,000$$$)  – the number of test cases. The description of test cases follows.

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

The second line of each test case contains a string $$$a$$$ of length $$$n$$$, consisting of only $$$0$$$ and $$$1$$$.

## Output Format
For each test case, output a string of length $$$n - 1$$$ consisting of $$$-$$$ and $$$+$$$ on a separate line. If there is more than one assignment of signs that produces the smallest possible absolute value, any of them is accepted.

## Examples
```input
3
2
11
5
01101
5
10001
```
```output
-
+-++
+++-
```

## Note
In the first test case, we can get the expression $$$1 - 1 = 0$$$, with absolute value $$$0$$$.

In the second test case, we can get the expression $$$0 + 1 - 1 + 0 + 1 = 1$$$, with absolute value $$$1$$$.

In the third test case, we can get the expression $$$1 + 0 + 0 + 0 - 1 = 0$$$, with absolute value $$$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 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
Little09 and his friends are playing a game. There are $$$n$$$ players, and the temperature value of the player $$$i$$$ is $$$i$$$.

The types of environment are expressed as $$$0$$$ or $$$1$$$. When two players fight in a specific environment, if its type is $$$0$$$, the player with a lower temperature value in this environment always wins; if it is $$$1$$$, the player with a higher temperature value in this environment always wins. The types of the $$$n-1$$$ environments form a binary string $$$s$$$ with a length of $$$n-1$$$.

If there are $$$x$$$ players participating in the game, there will be a total of $$$x-1$$$ battles, and the types of the $$$x-1$$$ environments will be the first $$$x-1$$$ characters of $$$s$$$. While there is more than one player left in the tournament, choose any two remaining players to fight. The player who loses will be eliminated from the tournament. The type of the environment of battle $$$i$$$ is $$$s_i$$$.

For each $$$x$$$ from $$$2$$$ to $$$n$$$, answer the following question: if all players whose temperature value does not exceed $$$x$$$ participate in the game, how many players have a chance to win?

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t \le 10^3$$$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$)  — the number of players.

The second line of each test case contains a binary string $$$s$$$ with a length $$$n-1$$$.

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

## Output Format
For each test case output $$$n-1$$$ integers  — for each $$$x$$$ from $$$2$$$ to $$$n$$$, output the number of players that have a chance to win.

## Examples
```input
2
4
001
4
101
```
```output
1 1 3 
1 2 3
```

## Note
In the first test case, for $$$x=2$$$ and $$$x=3$$$, only the player whose temperature value is $$$1$$$ can be the winner. For $$$x=4$$$, the player whose temperature value is $$$2,3,4$$$ can be the winner.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
ChthollyNotaSeniorious received a special gift from AquaMoon: $$$n$$$ binary arrays of length $$$m$$$. AquaMoon tells him that in one operation, he can choose any two arrays and any position $$$pos$$$ from $$$1$$$ to $$$m$$$, and swap the elements at positions $$$pos$$$ in these arrays.

He is fascinated with this game, and he wants to find the minimum number of operations needed to make the numbers of $$$1$$$s in all arrays the same. He has invited you to participate in this interesting game, so please try to find it!

If it is possible, please output specific exchange steps in the format described in the output section. Otherwise, please output $$$-1$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq m \leq 10^5$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains $$$m$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ $$$(0 \le a_{i, j} \le 1)$$$  — the elements of the $$$i$$$-th array.

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

## Output Format
For each test case, if the objective is not achievable, output $$$-1$$$.

Otherwise, in the first line output $$$k$$$ $$$(0 \le k \le mn)$$$  — the minimum number of operations required.

The $$$i$$$-th of the following $$$k$$$ lines should contain $$$3$$$ integers, $$$x_i, y_i, z_i$$$ $$$(1 \le x_i, y_i \le n, 1 \le z_i \le m)$$$, which describe an operation that swap $$$a_{x_i, z_i}, a_{y_i, z_i}$$$: swap the $$$z_i$$$-th number of the $$$x_i$$$-th and $$$y_i$$$-th arrays.

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

## Note
In the first test case, it's enough to do a single operation: to swap the first element in the second and the first rows. The arrays will become $$$[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$$$, each of them contains exactly two $$$1$$$s.

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
Cirno_9baka has a tree with $$$n$$$ nodes. He is willing to share it with you, which means you can operate on it.

Initially, there are two chess pieces on the node $$$1$$$ of the tree. In one step, you can choose any piece, and move it to the neighboring node. You are also given an integer $$$d$$$. You need to ensure that the distance between the two pieces doesn't ever exceed $$$d$$$.

Each of these two pieces has a sequence of nodes which they need to pass in any order, and eventually, they have to return to the root. As a curious boy, he wants to know the minimum steps you need to take.

## Input Format
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$2 \le d \le n \le 2\cdot 10^5$$$).

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$u_i, v_i$$$ $$$(1 \le u_i, v_i \le n)$$$, denoting the edge between the nodes $$$u_i, v_i$$$ of the tree.

It's guaranteed that these edges form a tree.

The next line contains an integer $$$m_1$$$ ($$$1 \le m_1 \le n$$$) and $$$m_1$$$ integers $$$a_1, a_2, \ldots, a_{m_1}$$$ ($$$1 \le a_i \le n$$$, all $$$a_i$$$ are distinct)  — the sequence of nodes that the first piece needs to pass.

The second line contains an integer $$$m_2$$$ ($$$1 \le m_2 \le n$$$) and $$$m_2$$$ integers $$$b_1, b_2, \ldots, b_{m_2}$$$ ($$$1 \le b_i \le n$$$, all $$$b_i$$$ are distinct)  — the sequence of nodes that the second piece needs to pass.

## Output Format
Output a single integer  — the minimum steps you need to take.

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

## Note
In the first sample, here is one possible sequence of steps of length $$$6$$$.

- The second piece moves by the route $$$1 \to 2 \to 4 \to 2 \to 1$$$.
- Then, the first piece moves by the route $$$1 \to 3 \to 1$$$.

In the second sample, here is one possible sequence of steps of length $$$8$$$:

- The first piece moves by the route $$$1 \to 2 \to 3$$$.
- Then, the second piece moves by the route $$$1 \to 2$$$.
- Then, the first piece moves by the route $$$3 \to 4 \to 3 \to 2 \to 1$$$.
- Then, the second piece moves by the route $$$2 \to 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 the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$ and $$$x$$$. You can make hacks only if both versions of the problem are solved.

Little09 has been interested in magic for a long time, and it's so lucky that he meets a magician! The magician will perform $$$n$$$ operations, each of them is one of the following three:

- $$$1\ x$$$: Create a pig with $$$x$$$ Health Points.
- $$$2\ x$$$: Reduce the Health Point of all living pigs by $$$x$$$.
- $$$3$$$: Repeat all previous operations. Formally, assuming that this is the $$$i$$$-th operation in the operation sequence, perform the first $$$i-1$$$ operations (including "Repeat" operations involved) in turn.

A pig will die when its Health Point is less than or equal to $$$0$$$.

Little09 wants to know how many living pigs there are after all the operations. Please, print the answer modulo $$$998\,244\,353$$$.

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

Each of the following $$$n$$$ lines contains an operation given in the form described in the problem statement. It's guaranteed that $$$1\leq x\leq 2\cdot 10^5$$$ in operations of the first two types.

## Output Format
Print a single integer  — the number of living pigs after all the operations, modulo $$$998\,244\,353$$$.

## Examples
```input
4
1 8
2 3
3
3
```
```output
2
```
-----
```input
6
1 5
1 6
2 2
3
1 4
3
```
```output
5
```
-----
```input
12
2 1
1 15
1 9
3
1 12
2 2
1 13
3
2 1
1 9
1 8
3
```
```output
17
```

## Note
In the first example, the operations are equivalent to repeating four times: create a pig with $$$8$$$ Health Points and then reduce the Health Points of all living pigs by $$$3$$$. It is easy to find that there are two living pigs in the end with $$$2$$$ and $$$5$$$ Health Points.

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 the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$ and $$$x$$$. You can make hacks only if both versions of the problem are solved.

Little09 has been interested in magic for a long time, and it's so lucky that he meets a magician! The magician will perform $$$n$$$ operations, each of them is one of the following three:

- $$$1\ x$$$: Create a pig with $$$x$$$ Health Points.
- $$$2\ x$$$: Reduce the Health Point of all living pigs by $$$x$$$.
- $$$3$$$: Repeat all previous operations. Formally, assuming that this is the $$$i$$$-th operation in the operation sequence, perform the first $$$i-1$$$ operations (including "Repeat" operations involved) in turn.

A pig will die when its Health Point is less than or equal to $$$0$$$.

Little09 wants to know how many living pigs there are after all the operations. Please, print the answer modulo $$$998\,244\,353$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1\leq n\leq 8\cdot 10^5$$$)  — the number of operations.

Each of the following $$$n$$$ lines contains an operation given in the form described in the problem statement. It's guaranteed that $$$1\leq x\leq 10^9$$$ in operations of the first two types.

## Output Format
Print a single integer  — the number of living pigs after all the operations, modulo $$$998\,244\,353$$$.

## Examples
```input
4
1 8
2 3
3
3
```
```output
2
```
-----
```input
6
1 5
1 6
2 2
3
1 4
3
```
```output
5
```
-----
```input
12
2 1
1 15
1 9
3
1 12
2 2
1 13
3
2 1
1 9
1 8
3
```
```output
17
```

## Note
In the first example, the operations are equivalent to repeating four times: create a pig with $$$8$$$ Health Points and then reduce the Health Points of all living pigs by $$$3$$$. It is easy to find that there are two living pigs in the end with $$$2$$$ and $$$5$$$ Health Points.

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 are two towers consisting of blocks of two colors: red and blue. Both towers are represented by strings of characters B and/or R denoting the order of blocks in them from the bottom to the top, where B corresponds to a blue block, and R corresponds to a red block.

These two towers are represented by strings BRBB and RBR.

You can perform the following operation any number of times: choose a tower with at least two blocks, and move its top block to the top of the other tower.

The pair of towers is beautiful if no pair of touching blocks has the same color; i. e. no red block stands on top of another red block, and no blue block stands on top of another blue block.

You have to check if it is possible to perform any number of operations (possibly zero) to make the pair of towers beautiful.

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

Each test case consists of three lines:

- the first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 20$$$) — the number of blocks in the first tower and the number of blocks in the second tower, respectively;
- the second line contains $$$s$$$ — a string of exactly $$$n$$$ characters B and/or R, denoting the first tower;
- the third line contains $$$t$$$ — a string of exactly $$$m$$$ characters B and/or R, denoting the second tower.

## Output Format
For each test case, print YES if it is possible to perform several (possibly zero) operations in such a way that the pair of towers becomes beautiful; otherwise print NO.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

## Examples
```input
4
4 3
BRBB
RBR
4 7
BRBR
RRBRBRB
3 4
RBR
BRBR
5 4
BRBRR
BRBR
```
```output
YES
YES
YES
NO
```

## Note
In the first test case, you can move the top block from the first tower to the second tower (see the third picture).

In the second test case, you can move the top block from the second tower to the first tower $$$6$$$ times.

In the third test case, the pair of towers is already beautiful.

Now solve the problem and return the code.