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
There is a group of $$$n$$$ people. Some of them might be liars, who always tell lies. Other people always tell the truth. The $$$i$$$-th person says "There are at least $$$l_i$$$ liars amongst us". Determine if what people are saying is contradictory, or if it is possible. If it is possible, output the number of liars in the group. If there are multiple possible answers, output any one of them.

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

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

The second line of each test case contains $$$n$$$ integers $$$l_i$$$ ($$$0 \leq l_i \leq n$$$) — the number said by the $$$i$$$-th person.

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$10^4$$$.

## Output Format
For each test case output a single integer. If what people are saying is contradictory, output $$$-1$$$. Otherwise, output the number of liars in the group. If there are multiple possible answers, output any one of them.

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

## Note
In the first example, the only possible answer is that the second person is a liar, so the answer is $$$1$$$ liar.

In the second example, it can be proven that we can't choose the liars so that all the requirements are satisfied.

In the third example, everybody tells the truth, so the answer is $$$0$$$ liars.

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 have an array $$$a$$$ of $$$n$$$ non-negative integers. Let's define $$$f(a, x) = [a_1 \bmod x, a_2 \bmod x, \dots, a_n \bmod x]$$$ for some positive integer $$$x$$$. Find the biggest $$$x$$$, such that $$$f(a, x)$$$ is a palindrome.

Here, $$$a \bmod x$$$ is the remainder of the integer division of $$$a$$$ by $$$x$$$.

An array is a palindrome if it reads the same backward as forward. More formally, an array $$$a$$$ of length $$$n$$$ is a palindrome if for every $$$i$$$ ($$$1 \leq i \leq n$$$) $$$a_i = a_{n - i + 1}$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$).

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$10^5$$$.

## Output Format
For each test case output the biggest $$$x$$$, such that $$$f(a, x)$$$ is a palindrome. If $$$x$$$ can be infinitely large, output $$$0$$$ instead.

## Examples
```input
4
2
1 2
8
3 0 1 2 0 3 2 1
1
0
3
100 1 1000000000
```
```output
1
2
0
999999900
```

## Note
In the first example, $$$f(a, x = 1) = [0, 0]$$$ which is a palindrome.

In the second example, $$$f(a, x = 2) = [1, 0, 1, 0, 0, 1, 0, 1]$$$ which is a palindrome.

It can be proven that in the first two examples, no larger $$$x$$$ satisfies the condition.

In the third example, $$$f(a, x) = [0]$$$ for any $$$x$$$, so we can choose it infinitely large, so the answer 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 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
There are $$$n$$$ programmers choosing their favorite algorithm amongst $$$m$$$ different choice options. Before the first round, all $$$m$$$ options are available. In each round, every programmer makes a vote for one of the remaining algorithms. After the round, only the algorithms with the maximum number of votes remain. The voting process ends when there is only one option left. Determine whether the voting process can continue indefinitely or no matter how people vote, they will eventually choose a single option after some finite amount of rounds?

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

Each test case consists of a single line containing two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^6$$$) — the number of people and choice options respectively.

## Output Format
For each test case output "YES" if the programmers will eventually choose a single option, and "NO" otherwise.

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as a positive answer).

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

## Note
In the first example, there are $$$8$$$ ways people could vote: $$$\{1|1|1, 1|1|2, 1|2|1, 1|2|2, 2|1|1, 2|1|2, 2|2|1, 2|2|2\}$$$.

In cases $$$1$$$, $$$2$$$, $$$3$$$, and $$$5$$$, the programmers are left with the first algorithm, and in the remaining cases people are left with the second one, so the voting ends in one round in any case.

In the second example, the programmers could always vote $$$1|1|2|2$$$. Both algorithms have the maximum number of votes and remain for the next round, so the voting never ends.

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There is a street with $$$n$$$ sights, with sight number $$$i$$$ being $$$i$$$ miles from the beginning of the street. Sight number $$$i$$$ has beauty $$$b_i$$$. You want to start your morning jog $$$l$$$ miles and end it $$$r$$$ miles from the beginning of the street. By the time you run, you will see sights you run by (including sights at $$$l$$$ and $$$r$$$ miles from the start). You are interested in the $$$3$$$ most beautiful sights along your jog, but every mile you run, you get more and more tired.

So choose $$$l$$$ and $$$r$$$, such that there are at least $$$3$$$ sights you run by, and the sum of beauties of the $$$3$$$ most beautiful sights minus the distance in miles you have to run is maximized. More formally, choose $$$l$$$ and $$$r$$$, such that $$$b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$$$ is maximum possible, where $$$i_1, i_2, i_3$$$ are the indices of the three maximum elements in range $$$[l, r]$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$b_i$$$ ($$$1 \leq b_i \leq 10^8$$$) — beauties of sights $$$i$$$ miles from the beginning of the street.

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$10^5$$$.

## Output Format
For each test case output a single integer equal to the maximum value $$$b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$$$ for some running range $$$[l, r]$$$.

## Examples
```input
4
5
5 1 4 2 3
4
1 1 1 1
6
9 8 7 6 5 4
7
100000000 1 100000000 1 100000000 1 100000000
```
```output
8
1
22
299999996
```

## Note
In the first example, we can choose $$$l$$$ and $$$r$$$ to be $$$1$$$ and $$$5$$$. So we visit all the sights and the three sights with the maximum beauty are the sights with indices $$$1$$$, $$$3$$$, and $$$5$$$ with beauties $$$5$$$, $$$4$$$, and $$$3$$$, respectively. So the total value is $$$5 + 4 + 3 - (5 - 1) = 8$$$.

In the second example, the range $$$[l, r]$$$ can be $$$[1, 3]$$$ or $$$[2, 4]$$$, the total value is $$$1 + 1 + 1 - (3 - 1) = 1$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There is a string $$$a$$$ (unknown to you), consisting of lowercase Latin letters, encrypted according to the following rule into string $$$s$$$:

- after each character of string $$$a$$$, an arbitrary (possibly zero) number of any lowercase Latin letters, different from the character itself, is added;
- after each such addition, the character that we supplemented is added.

You are given string $$$s$$$, and you need to output the initial string $$$a$$$. In other words, you need to decrypt string $$$s$$$.

Note that each string encrypted in this way is decrypted uniquely.

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

The descriptions of the test cases follow.

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

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ — the encrypted message obtained from some string $$$a$$$.

## Output Format
For each test case, output the decrypted message $$$a$$$ on a separate line.

## Examples
```input
3
8
abacabac
5
qzxcq
20
ccooddeeffoorrcceess
```
```output
ac
q
codeforces
```

## Note
In the first encrypted message, the letter $$$a$$$ is encrypted as $$$aba$$$, and the letter $$$c$$$ is encrypted as $$$cabac$$$.

In the second encrypted message, only one letter $$$q$$$ is encrypted as $$$qzxcq$$$.

In the third encrypted message, zero characters are added to each letter.

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
Dima Vatrushin is a math teacher at school. He was sent on vacation for $$$n$$$ days for his good work. Dima has long dreamed of going to a ski resort, so he wants to allocate several consecutive days and go skiing. Since the vacation requires careful preparation, he will only go for at least $$$k$$$ days.

You are given an array $$$a$$$ containing the weather forecast at the resort. That is, on the $$$i$$$-th day, the temperature will be $$$a_i$$$ degrees.

Dima was born in Siberia, so he can go on vacation only if the temperature does not rise above $$$q$$$ degrees throughout the vacation.

Unfortunately, Dima was so absorbed in abstract algebra that he forgot how to count. He asks you to help him and count the number of ways to choose vacation dates at the resort.

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

Then follow the descriptions of the test cases.

The first line of each test case contains three integers $$$n$$$, $$$k$$$, $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$, $$$-10^9 \le q \le 10^9$$$) — the length of the array $$$a$$$, the minimum number of days at the resort, and the maximum comfortable temperature for Dima.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the temperature at the ski resort.

The sum of all $$$n$$$ values over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Output $$$t$$$ integers, each of which is the answer to the corresponding test case — the number of ways for Dima to choose vacation dates at the resort.

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

## Note
In the first test case of the example, Dima can go on any day, so the suitable dates for him are [1], [2], [3], [1, 2], [2, 3], [1, 2, 3].

In the second and fourth test cases of the example, Dima cannot go on any day due to the high temperature, so there are no suitable dates.

In the third test case of the example, Dima can only go on the dates [1, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two positive integers, $$$a$$$ and $$$b$$$ ($$$a < b$$$).

For some positive integer $$$n$$$, two players will play a game starting with a pile of $$$n$$$ stones. They take turns removing exactly $$$a$$$ or exactly $$$b$$$ stones from the pile. The player who is unable to make a move loses.

Find a positive integer $$$n$$$ such that the second player to move in this game has a winning strategy. This means that no matter what moves the first player makes, the second player can carefully choose their moves (possibly depending on the first player's moves) to ensure they win.

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

The only line of each test case contains two integers, $$$a$$$ and $$$b$$$ ($$$1 \le a < b \le 100$$$).

## Output Format
For each test case, output any positive integer $$$n$$$ ($$$1 \le n \le 10^6$$$) such that the second player to move wins.

It can be proven that such an $$$n$$$ always exists under the constraints of the problem.

## Examples
```input
3
1 4
1 5
9 26
```
```output
2
6
3
```

## Note
In the first test case, when $$$n = 2$$$, the first player must remove $$$a = 1$$$ stone. Then, the second player can respond by removing $$$a = 1$$$ stone. The first player can no longer make a move, so the second player wins.

In the second test case, when $$$n = 6$$$, the first player has two options:

- If they remove $$$b = 5$$$ stones, then the second player can respond by removing $$$a = 1$$$ stone. The first player can no longer make a move, so the second player wins.
- If they remove $$$a = 1$$$ stone, then the second player can respond by removing $$$a = 1$$$ stone. Afterwards, the players can only alternate removing exactly $$$a = 1$$$ stone. The second player will take the last stone and win.

In the third test case, the first player cannot make any moves when $$$n = 3$$$, so the second player immediately wins.

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 positive integer $$$n$$$.

In this problem, the $$$\operatorname{MEX}$$$ of a collection of integers $$$c_1,c_2,\dots,c_k$$$ is defined as the smallest positive integer $$$x$$$ which does not occur in the collection $$$c$$$.

The primality of an array $$$a_1,\dots,a_n$$$ is defined as the number of pairs $$$(l,r)$$$ such that $$$1 \le l \le r \le n$$$ and $$$\operatorname{MEX}(a_l,\dots,a_r)$$$ is a prime number.

Find any permutation of $$$1,2,\dots,n$$$ with the maximum possible primality among all permutations of $$$1,2,\dots,n$$$.

Note:

- A prime number is a number greater than or equal to $$$2$$$ that is not divisible by any positive integer except $$$1$$$ and itself. For example, $$$2,5,13$$$ are prime numbers, but $$$1$$$ and $$$6$$$ are not prime numbers.
- A permutation of $$$1,2,\dots,n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \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 $$$n$$$ integers: a permutation of $$$1,2,\dots,n$$$ that achieves the maximum possible primality.

If there are multiple solutions, print any of them.

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

## Note
In the first test case, there are $$$3$$$ pairs $$$(l,r)$$$ with $$$1 \le l \le r \le 2$$$, out of which $$$2$$$ have a prime $$$\operatorname{MEX}(a_l,\dots,a_r)$$$:

- $$$(l,r) = (1,1)$$$: $$$\operatorname{MEX}(2) = 1$$$, which is not prime.
- $$$(l,r) = (1,2)$$$: $$$\operatorname{MEX}(2,1) = 3$$$, which is prime.
- $$$(l,r) = (2,2)$$$: $$$\operatorname{MEX}(1) = 2$$$, which is prime.

In the second test case, $$$\operatorname{MEX}(1) = 2$$$ is prime, so the primality is $$$1$$$.

In the third test case, the maximum possible primality is $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have discovered $$$n$$$ mysterious particles on a line with integer charges of $$$c_1,\dots,c_n$$$. You have a device that allows you to perform the following operation:

- Choose a particle and remove it from the line. The remaining particles will shift to fill in the gap that is created. If there were particles with charges $$$x$$$ and $$$y$$$ directly to the left and right of the removed particle, they combine into a single particle of charge $$$x+y$$$.

For example, if the line of particles had charges of $$$[-3,1,4,-1,5,-9]$$$, performing the operation on the $$$4$$$th particle will transform the line into $$$[-3,1,9,-9]$$$.

If we then use the device on the $$$1$$$st particle in this new line, the line will turn into $$$[1,9,-9]$$$.

You will perform operations until there is only one particle left. What is the maximum charge of this remaining particle that you can obtain?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The 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 second line of each test case contains $$$n$$$ integers $$$c_1,\dots,c_n$$$ ($$$-10^9 \le c_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 one integer, the maximum charge of the remaining particle.

## Examples
```input
3
6
-3 1 4 -1 5 -9
5
998244353 998244353 998244353 998244353 998244353
1
-2718
```
```output
9
2994733059
-2718
```

## Note
In the first test case, the best strategy is to use the device on the $$$4$$$th particle, then on the $$$1$$$st particle (as described in the statement), and finally use the device on the new $$$3$$$rd particle followed by the $$$1$$$st particle.

In the second test case, the best strategy is to use the device on the $$$4$$$th particle to transform the line into $$$[998244353,998244353,1996488706]$$$, then on the $$$2$$$nd particle to transform the line into $$$[2994733059]$$$. Be wary of integer overflow.

In the third test case, there is only one particle, so no operations can be performed.

Now solve the problem and return the code.