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
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 python3.

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

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

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

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

# Problem
YunQian is standing on an infinite plane with the Cartesian coordinate system on it. In one move, she can move to the diagonally adjacent point on the top right or the adjacent point on the left.

That is, if she is standing on point $$$(x,y)$$$, she can either move to point $$$(x+1,y+1)$$$ or point $$$(x-1,y)$$$.

YunQian initially stands at point $$$(a,b)$$$ and wants to move to point $$$(c,d)$$$. Find the minimum number of moves she needs to make or declare that it is impossible.

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

The first line and only line of each test case contain four integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ ($$$-10^8\le a,b,c,d\le 10^8$$$).

## Output Format
For each test case, if it is possible to move from point $$$(a,b)$$$ to point $$$(c,d)$$$, output the minimum number of moves. Otherwise, output $$$-1$$$.

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

## Note
In the first test case, one possible way using $$$4$$$ moves is $$$(-1,0)\to (0,1)\to (-1,1)\to (0,2)\to (-1,2)$$$. It can be proven that it is impossible to move from point $$$(-1,0)$$$ to point $$$(-1,2)$$$ in less than $$$4$$$ moves.

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

# Problem
You are given an array $$$a$$$ of length $$$n$$$. The score of $$$a$$$ is the MEX$$$^{\dagger}$$$ of $$$[a_1+a_2,a_2+a_3,\ldots,a_{n-1}+a_n]$$$. Find the minimum score of $$$a$$$ if you are allowed to rearrange elements of $$$a$$$ in any order. Note that you are not required to construct the array $$$a$$$ that achieves the minimum score.

$$$^{\dagger}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

- The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
- The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
- The MEX of $$$[0,3,1,2]$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 2\cdot 10^5$$$).

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, output the minimum score of $$$a$$$ after rearranging the elements of $$$a$$$ in any order.

## Examples
```input
3
2
0 0
3
0 0 1
8
1 0 0 0 2 0 3 0
```
```output
1
0
1
```

## Note
In the first test case, it is optimal to rearrange $$$a$$$ as $$$[0,0]$$$, the score of this array is the MEX of $$$[0+0]=[0]$$$, which is $$$1$$$.

In the second test case, it is optimal to rearrange $$$a$$$ as $$$[0,1,0]$$$, the score of this array is the MEX of $$$[0+1,1+0]=[1,1]$$$, which is $$$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: 1024.0 MB

# Problem
For some positive integer $$$m$$$, YunQian considers an array $$$q$$$ of $$$2m$$$ (possibly negative) integers good, if and only if for every possible subsequence of $$$q$$$ that has length $$$m$$$, the product of the $$$m$$$ elements in the subsequence is equal to the sum of the $$$m$$$ elements that are not in the subsequence. Formally, let $$$U=\{1,2,\ldots,2m\}$$$. For all sets $$$S \subseteq U$$$ such that $$$|S|=m$$$, $$$\prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i$$$.

Define the distance between two arrays $$$a$$$ and $$$b$$$ both of length $$$k$$$ to be $$$\sum\limits_{i=1}^k|a_i-b_i|$$$.

You are given a positive integer $$$n$$$ and an array $$$p$$$ of $$$2n$$$ integers.

Find the minimum distance between $$$p$$$ and $$$q$$$ over all good arrays $$$q$$$ of length $$$2n$$$. It can be shown for all positive integers $$$n$$$, at least one good array exists. Note that you are not required to construct the array $$$q$$$ that achieves this minimum distance.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot10^5$$$).

The second line of each test case contains $$$2n$$$ integers $$$p_1, p_2, \ldots, p_{2n}$$$ ($$$|p_i| \le 10^9$$$).

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, output the minimum distance between $$$p$$$ and a good $$$q$$$.

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

## Note
In the first test case, it is optimal to let $$$q=[6,6]$$$.

In the second test case, it is optimal to let $$$q=[2,2,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: 3.0 seconds
Memory limit: 1024.0 MB

# Problem
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$m$$$. You can make hacks only if both versions of the problem are solved.

You are given an array $$$a$$$ of length $$$n$$$ and two integers $$$m$$$ and $$$k$$$. Each element in $$$a$$$ satisfies $$$1\le a_i \le m$$$.

In one operation, you choose two indices $$$i$$$ and $$$j$$$ such that $$$1 \le i < j \le |a|$$$, then append $$$\gcd(a_i,a_j)$$$ to the back of the array and delete $$$a_i$$$ and $$$a_j$$$ from the array. Note that the length of the array decreases by one after this operation.

Find the maximum possible sum of the array after performing exactly $$$k$$$ operations.

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

The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$; $$$1\le m \le 10^6$$$; $$$1 \le k \le n-1$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le m$$$).

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

## Output Format
For each test case, output the maximum possible sum of the array after performing $$$k$$$ operations optimally.

## Examples
```input
3
3 8 1
4 7 8
5 114 2
7 2 4 1 6
3 514 2
2 3 3
```
```output
11
14
1
```

## Note
In the first test case, the best way is to choose $$$i=1$$$, $$$j=3$$$ in the first operation. The final sequence is $$$[7,4]$$$.

Now solve the problem and return the code.