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 was dismantling his attic and found an old floppy drive on it. A round disc was inserted into the drive with $$$n$$$ integers written on it.

Polycarp wrote the numbers from the disk into the $$$a$$$ array. It turned out that the drive works according to the following algorithm:

- the drive takes one positive number $$$x$$$ as input and puts a pointer to the first element of the $$$a$$$ array;
- after that, the drive starts rotating the disk, every second moving the pointer to the next element, counting the sum of all the elements that have been under the pointer. Since the disk is round, in the $$$a$$$ array, the last element is again followed by the first one;
- as soon as the sum is at least $$$x$$$, the drive will shut down.

Polycarp wants to learn more about the operation of the drive, but he has absolutely no free time. So he asked you $$$m$$$ questions. To answer the $$$i$$$-th of them, you need to find how many seconds the drive will work if you give it $$$x_i$$$ as input. Please note that in some cases the drive can work infinitely.

For example, if $$$n=3, m=3$$$, $$$a=[1, -3, 4]$$$ and $$$x=[1, 5, 2]$$$, then the answers to the questions are as follows:

- the answer to the first query is $$$0$$$ because the drive initially points to the first item and the initial sum is $$$1$$$.
- the answer to the second query is $$$6$$$, the drive will spin the disk completely twice and the amount becomes $$$1+(-3)+4+1+(-3)+4+1=5$$$.
- the answer to the third query is $$$2$$$, the amount is $$$1+(-3)+4=2$$$.

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

The first line of each test case consists of two positive integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of numbers on the disk and the number of asked questions.

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

The third line of each test case contains $$$m$$$ positive integers $$$x_1, x_2, \ldots, x_m$$$ ($$$1 \le x \le 10^9$$$).

It is guaranteed that the sums of $$$n$$$ and $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

## Output Format
Print $$$m$$$ numbers on a separate line for each test case. The $$$i$$$-th number is:

- $$$-1$$$ if the drive will run infinitely;
- the number of seconds the drive will run, otherwise.

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

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
This week Arkady wanted to cook some pancakes (to follow ancient traditions) and make a problem about that. But then he remembered that one can't make a problem about stacking pancakes without working at a specific IT company, so he decided to bake the Napoleon cake instead.

To bake a Napoleon cake, one has to bake $$$n$$$ dry layers first, and then put them on each other in one stack, adding some cream. Arkady started with an empty plate, and performed the following steps $$$n$$$ times:

- place a new cake layer on the top of the stack;
- after the $$$i$$$-th layer is placed, pour $$$a_i$$$ units of cream on top of the stack.

When $$$x$$$ units of cream are poured on the top of the stack, top $$$x$$$ layers of the cake get drenched in the cream. If there are less than $$$x$$$ layers, all layers get drenched and the rest of the cream is wasted. If $$$x = 0$$$, no layer gets drenched.

The picture represents the first test case of the example.

Help Arkady determine which layers of the cake eventually get drenched when the process is over, and which don't.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 20\,000$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of layers in the cake.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — the amount of cream poured on the cake after adding each layer.

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

## Output Format
For each test case, print a single line with $$$n$$$ integers. The $$$i$$$-th of the integers should be equal to $$$1$$$ if the $$$i$$$-th layer from the bottom gets drenched, and $$$0$$$ otherwise.

## Examples
```input
3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0
```
```output
1 1 0 1 1 1 
0 1 1 1 1 1 0 0 1 1 
0 0 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
Sayaka Saeki is a member of the student council, which has $$$n$$$ other members (excluding Sayaka). The $$$i$$$-th member has a height of $$$a_i$$$ millimeters.

It's the end of the school year and Sayaka wants to take a picture of all other members of the student council. Being the hard-working and perfectionist girl as she is, she wants to arrange all the members in a line such that the amount of photogenic consecutive pairs of members is as large as possible.

A pair of two consecutive members $$$u$$$ and $$$v$$$ on a line is considered photogenic if their average height is an integer, i.e. $$$\frac{a_u + a_v}{2}$$$ is an integer.

Help Sayaka arrange the other members to maximize the number of photogenic consecutive pairs.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2000$$$)  — the number of other council members.

The second line of each test case contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$)  — the heights of each of the other members in millimeters.

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

## Output Format
For each test case, output on one line $$$n$$$ integers representing the heights of the other members in the order, which gives the largest number of photogenic consecutive pairs. If there are multiple such orders, output any of them.

## Examples
```input
4
3
1 1 2
3
1 1 1
8
10 9 13 15 3 16 9 13
2
18 9
```
```output
1 1 2 
1 1 1 
13 9 13 15 3 9 16 10 
9 18
```

## Note
In the first test case, there is one photogenic pair: $$$(1, 1)$$$ is photogenic, as $$$\frac{1+1}{2}=1$$$ is integer, while $$$(1, 2)$$$ isn't, as $$$\frac{1+2}{2}=1.5$$$ isn't integer.

In the second test case, both pairs are photogenic.

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
The student council has a shared document file. Every day, some members of the student council write the sequence TMT (short for Towa Maji Tenshi) in it.

However, one day, the members somehow entered the sequence into the document at the same time, creating a jumbled mess. Therefore, it is Suguru Doujima's task to figure out whether the document has malfunctioned. Specifically, he is given a string of length $$$n$$$ whose characters are all either T or M, and he wants to figure out if it is possible to partition it into some number of disjoint subsequences, all of which are equal to TMT. That is, each character of the string should belong to exactly one of the subsequences.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero) characters.

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

The first line of each test case contains an integer $$$n$$$ ($$$3 \le n < 10^5$$$), the number of characters in the string entered in the document. It is guaranteed that $$$n$$$ is divisible by $$$3$$$.

The second line of each test case contains a string of length $$$n$$$ consisting of only the characters T and M.

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

## Output Format
For each test case, print a single line containing YES if the described partition exists, and a single line containing NO otherwise.

## Examples
```input
5
3
TMT
3
MTT
6
TMTMTT
6
TMTTTT
6
TTMMTT
```
```output
YES
NO
YES
NO
YES
```

## Note
In the first test case, the string itself is already a sequence equal to TMT.

In the third test case, we may partition the string into the subsequences TMTMTT. Both the bolded and the non-bolded subsequences are equal to TMT.

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

# Problem
Today we will be playing a red and white colouring game (no, this is not the Russian Civil War; these are just the colours of the Canadian flag).

You are given an $$$n \times m$$$ grid of "R", "W", and "." characters. "R" is red, "W" is white and "." is blank. The neighbours of a cell are those that share an edge with it (those that only share a corner do not count).

Your job is to colour the blank cells red or white so that every red cell only has white neighbours (and no red ones) and every white cell only has red neighbours (and no white ones). You are not allowed to recolour already coloured cells.

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

In each test case, the first line will contain $$$n$$$ ($$$1 \le n \le 50$$$) and $$$m$$$ ($$$1 \le m \le 50$$$), the height and width of the grid respectively.

The next $$$n$$$ lines will contain the grid. Each character of the grid is either 'R', 'W', or '.'.

## Output Format
For each test case, output "YES" if there is a valid grid or "NO" if there is not.

If there is, output the grid on the next $$$n$$$ lines. If there are multiple answers, print any.

In the output, the "YES"s and "NO"s are case-insensitive, meaning that outputs such as "yEs" and "nO" are valid. However, the grid is case-sensitive.

## Examples
```input
3
4 6
.R....
......
......
.W....
4 4
.R.W
....
....
....
5 1
R
W
R
W
R
```
```output
YES
WRWRWR
RWRWRW
WRWRWR
RWRWRW
NO
YES
R
W
R
W
R
```

## Note
The answer for the first example case is given in the example output, and it can be proven that no grid exists that satisfies the requirements of the second example case. In the third example all cells are initially coloured, and the colouring is valid.

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

# Problem
When he's not training for IOI, Little Alawn enjoys playing with puzzles of various types to stimulate his brain. Today, he's playing with a puzzle that consists of a $$$2 \times n$$$ grid where each row is a permutation of the numbers $$$1,2,3,\ldots,n$$$.

The goal of Little Alawn's puzzle is to make sure no numbers on the same column or row are the same (we'll call this state of the puzzle as solved), and to achieve this he is able to swap the numbers in any column. However, after solving the puzzle many times, Little Alawn got bored and began wondering about the number of possible solved configurations of the puzzle he could achieve from an initial solved configuration only by swapping numbers in a column.

Unfortunately, Little Alawn got stuck while trying to solve this harder problem, so he was wondering if you could help him with it. Find the answer modulo $$$10^9+7$$$.

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

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

The next two lines of each test case describe the initial state of the puzzle grid. Each line will be a permutation of the numbers $$$1,2,3,\ldots,n$$$ and the numbers in each column and row will be pairwise distinct.

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

## Output Format
For each test case output a single integer, the number of possible solved configurations of the puzzle Little Alawn can achieve from an initial solved configuration only by swapping numbers in a column. As the answer can be very large, please output it modulo $$$10^9+7$$$.

The answer for each test case should be on a separate line.

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

## Note
The two possible puzzle configurations for example $$$1$$$ are:

- $$$[1,4,2,3]$$$ in the first row and $$$[3,2,1,4]$$$ in the second;
- $$$[3,2,1,4]$$$ in the first row and $$$[1,4,2,3]$$$ in the second.

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
Annie has gotten bored of winning every coding contest and farming unlimited rating. Today, she is going to farm potatoes instead.

Annie's garden is an infinite 2D plane. She has $$$n$$$ potatoes to plant, and the $$$i$$$-th potato must be planted at $$$(x_i,y_i)$$$. Starting at the point $$$(0, 0)$$$, Annie begins walking, in one step she can travel one unit right or up (increasing her $$$x$$$ or $$$y$$$ coordinate by $$$1$$$ respectively). At any point $$$(X,Y)$$$ during her walk she can plant some potatoes at arbitrary points using her potato gun, consuming $$$\max(|X-x|,|Y-y|)$$$ units of energy in order to plant a potato at $$$(x,y)$$$. Find the minimum total energy required to plant every potato.

Note that Annie may plant any number of potatoes from any point.

## Input Format
The first line contains the integer $$$n$$$ ($$$1 \le n \le 800\,000$$$).

The next $$$n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i,y_i \le 10^9$$$), representing the location of the $$$i$$$-th potato. It is possible that some potatoes should be planted in the same location.

## Output Format
Print the minimum total energy to plant all potatoes.

## Examples
```input
2
1 1
2 2
```
```output
0
```
-----
```input
2
1 1
2 0
```
```output
1
```
-----
```input
3
5 5
7 7
4 9
```
```output
2
```
-----
```input
10
5 1
4 0
9 6
0 2
10 1
9 10
3 10
0 10
8 9
1 5
```
```output
19
```
-----
```input
10
1 1
2 2
2 0
4 2
4 0
2 0
0 2
4 0
4 2
5 1
```
```output
6
```

## Note
In example $$$1$$$, Annie can travel to each spot directly and plant a potato with no energy required.

In example $$$2$$$, moving to $$$(1,0)$$$, Annie plants the second potato using $$$1$$$ energy. Next, she travels to $$$(1,1)$$$ and plants the first potato with $$$0$$$ energy.

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 a multiset (i. e. a set that can contain multiple equal integers) containing $$$2n$$$ integers. Determine if you can split it into exactly $$$n$$$ pairs (i. e. each element should be in exactly one pair) so that the sum of the two elements in each pair is odd (i. e. when divided by $$$2$$$, the remainder is $$$1$$$).

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t\leq 100$$$) — the number of test cases. The description of the test cases follows.

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

The second line of each test case contains $$$2n$$$ integers $$$a_1,a_2,\dots, a_{2n}$$$ ($$$0\leq a_i\leq 100$$$) — the numbers in the set.

## Output Format
For each test case, print "Yes" if it can be split into exactly $$$n$$$ pairs so that the sum of the two elements in each pair is odd, and "No" otherwise. You can print each letter in any case.

## Examples
```input
5
2
2 3 4 5
3
2 3 4 5 5 5
1
2 4
1
2 3
4
1 5 3 2 6 7 3 4
```
```output
Yes
No
No
Yes
No
```

## Note
In the first test case, a possible way of splitting the set is $$$(2,3)$$$, $$$(4,5)$$$.

In the second, third and fifth test case, we can prove that there isn't any possible way.

In the fourth test case, a possible way of splitting the set is $$$(2,3)$$$.

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
There is an infinite set generated as follows:

- $$$1$$$ is in this set.
- If $$$x$$$ is in this set, $$$x \cdot a$$$ and $$$x+b$$$ both are in this set.

For example, when $$$a=3$$$ and $$$b=6$$$, the five smallest elements of the set are:

- $$$1$$$,
- $$$3$$$ ($$$1$$$ is in this set, so $$$1\cdot a=3$$$ is in this set),
- $$$7$$$ ($$$1$$$ is in this set, so $$$1+b=7$$$ is in this set),
- $$$9$$$ ($$$3$$$ is in this set, so $$$3\cdot a=9$$$ is in this set),
- $$$13$$$ ($$$7$$$ is in this set, so $$$7+b=13$$$ is in this set).

Given positive integers $$$a$$$, $$$b$$$, $$$n$$$, determine if $$$n$$$ is in this set.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t\leq 10^5$$$) — the number of test cases. The description of the test cases follows.

The only line describing each test case contains three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1\leq n,a,b\leq 10^9$$$) separated by a single space.

## Output Format
For each test case, print "Yes" if $$$n$$$ is in this set, and "No" otherwise. You can print each letter in any case.

## Examples
```input
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264
```
```output
Yes
No
Yes
No
Yes
```

## Note
In the first test case, $$$24$$$ is generated as follows:

- $$$1$$$ is in this set, so $$$3$$$ and $$$6$$$ are in this set;
- $$$3$$$ is in this set, so $$$9$$$ and $$$8$$$ are in this set;
- $$$8$$$ is in this set, so $$$24$$$ and $$$13$$$ are in this set.

Thus we can see $$$24$$$ is in this set.

The five smallest elements of the set in the second test case is described in statements. We can see that $$$10$$$ isn't among them.

Now solve the problem and return the code.