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

# Problem
You're given a multiset of non-negative integers $$$\{a_1, a_2, \dots, a_n\}$$$.

In one step you take two elements $$$x$$$ and $$$y$$$ of the multiset, remove them and insert their mean value $$$\frac{x + y}{2}$$$ back into the multiset.

You repeat the step described above until you are left with only two numbers $$$A$$$ and $$$B$$$. What is the maximum possible value of their absolute difference $$$|A-B|$$$?

Since the answer is not an integer number, output it 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 100$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the size of the multiset.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the multiset.

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

## Output Format
For each test case, output a single integer, the answer to the problem modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output an integer $$$x$$$ such that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Examples
```input
5
2
7 3
4
1 2 10 11
3
1 2 3
6
64 32 64 16 64 0
4
1 1 1 1
```
```output
4
9
500000005
59
0
```

## Note
In the first case, you can't do any operations, so the answer is $$$|7-3|=4$$$.

In the second case, one of the optimal sequence of operations:

1. Substitute $$$1$$$ and $$$2$$$ with $$$1.5$$$;
2. Substitute $$$10$$$ and $$$11$$$ with $$$10.5$$$;
3. The difference between $$$1.5$$$ and $$$10.5$$$ is $$$9$$$.

In the third case, the exact answer is $$$\frac{3}{2}$$$, and $$$500\,000\,005 \cdot 2 \equiv 3 \pmod{10^9+7}$$$.

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
You are given a string $$$s$$$. A pair of its non-empty substrings $$$(a, b)$$$ is called entangled if there is a (possibly empty) link string $$$c$$$ such that:

- Every occurrence of $$$a$$$ in $$$s$$$ is immediately followed by $$$cb$$$;
- Every occurrence of $$$b$$$ in $$$s$$$ is immediately preceded by $$$ac$$$.

In other words, $$$a$$$ and $$$b$$$ occur in $$$s$$$ only as substrings of $$$acb$$$. Compute the total number of entangled pairs of substrings of $$$s$$$.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.

## Input Format
The first and only line contains a string $$$s$$$ of lowercase English letters ($$$1 \leq |s| \leq 10^5$$$) — the string for which you should count pairs of entangled substrings.

## Output Format
Output a single integer, the number of entangled pairs of substrings of $$$s$$$.

## Examples
```input
abba
```
```output
1
```
-----
```input
abacaba
```
```output
0
```
-----
```input
abcabcabcabc
```
```output
5
```
-----
```input
adamant
```
```output
82
```

## Note
In the first example, the only entangled pair is (ab,ba). For this pair, the corresponding link string $$$c$$$ is empty, as they only occur as substrings of the whole string abba, which doesn't have any characters between ab and ba.

In the second example, there are no entangled pairs.

In the third example, the entangled pairs are (a,b), (b,c), (a,c), (a,bc), and (ab,c). For most pairs, the corresponding link string $$$c$$$ is empty, except for the pair (a,c), for which the link string $$$c$$$ is b, as a and c only occur as substrings of the string abc.

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

# Problem
Consider an array $$$a_1, a_2, \dots, a_n$$$ consisting of numbers $$$1$$$ and $$$-1$$$. Define $$$A$$$-characteristic of this array as a number of pairs of indices $$$1 \le i < j \le n$$$, such that $$$a_i \cdot a_j = 1$$$.

Find any array $$$a$$$ with given length $$$n$$$ with $$$A$$$-characteristic equal to the given value $$$k$$$.

## 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 $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100$$$; $$$0 \le k \le \frac{(n-1) n}{2}$$$) — the length of required array and required $$$A$$$-characteristic.

## Output Format
For each test case, if there is no array $$$a$$$ with given $$$A$$$-characteristic $$$k$$$, print NO.

Otherwise, print YES and $$$n$$$ numbers $$$1$$$ and $$$-1$$$, which form the required array $$$a$$$. If there are multiple answers, print any of them.

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

## Note
In the first test case, there is only one pair of different elements in the array, and their product is $$$a_1 \cdot a_2 = -1 \neq 1$$$, hence its $$$A$$$-characteristic is $$$0$$$.

In the second test case, there is only one pair of different elements in the array, and their product is $$$a_1 \cdot a_2 = 1$$$, hence its $$$A$$$-characteristic is $$$1$$$.

In the third test case, there are three pairs of different elements in the array, and their product are: $$$a_1 \cdot a_2 = -1$$$, $$$a_1 \cdot a_3 = 1$$$, $$$a_2 \cdot a_3 = -1$$$, hence its $$$A$$$-characteristic is $$$1$$$.

In the fourth test case, we can show, that there is no array with length $$$3$$$, which $$$A$$$-characteristic is $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Alice and Bob are playing a game on a graph. They have an undirected graph without self-loops and multiple edges. All vertices of the graph have degree equal to $$$2$$$. The graph may consist of several components. Note that if such graph has $$$n$$$ vertices, it will have exactly $$$n$$$ edges.

Alice and Bob take turn. Alice goes first. In each turn, the player can choose $$$k$$$ ($$$l \le k \le r$$$; $$$l < r$$$) vertices that form a connected subgraph and erase these vertices from the graph, including all incident edges.

The player who can't make a step loses.

For example, suppose they are playing on the given graph with given $$$l = 2$$$ and $$$r = 3$$$:

A valid vertex set for Alice to choose at the first move is one of the following:

- $$$\{1, 2\}$$$
- $$$\{1, 3\}$$$
- $$$\{2, 3\}$$$
- $$$\{4, 5\}$$$
- $$$\{4, 6\}$$$
- $$$\{5, 6\}$$$
- $$$\{1, 2, 3\}$$$
- $$$\{4, 5, 6\}$$$

Then a valid vertex set for Bob to choose at the first move is one of the following:

- $$$\{1, 2\}$$$
- $$$\{1, 3\}$$$
- $$$\{2, 3\}$$$
- $$$\{1, 2, 3\}$$$

Alice can't make a move, so she loses.

You are given a graph of size $$$n$$$ and integers $$$l$$$ and $$$r$$$. Who will win if both Alice and Bob play optimally.

## Input Format
The first line contains three integers $$$n$$$, $$$l$$$ and $$$r$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le l < r \le n$$$) — the number of vertices in the graph, and the constraints on the number of vertices Alice or Bob can choose in one move.

Next $$$n$$$ lines contains edges of the graph: one edge per line. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — description of the $$$i$$$-th edge.

It's guaranteed that the degree of each vertex of the given graph is equal to $$$2$$$.

## Output Format
Print Alice (case-insensitive) if Alice wins, or Bob otherwise.

## Examples
```input
6 2 3
1 2
2 3
3 1
4 5
5 6
6 4
```
```output
Bob
```
-----
```input
6 1 2
1 2
2 3
3 1
4 5
5 6
6 4
```
```output
Bob
```
-----
```input
12 1 3
1 2
2 3
3 1
4 5
5 6
6 7
7 4
8 9
9 10
10 11
11 12
12 8
```
```output
Alice
```

## Note
In the first test the same input as in legend is shown.

In the second test the same graph as in legend is shown, but with $$$l = 1$$$ and $$$r = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
No, not "random" numbers.

Ranom digits are denoted by uppercase Latin letters from A to E. Moreover, the value of the letter A is $$$1$$$, B is $$$10$$$, C is $$$100$$$, D is $$$1000$$$, E is $$$10000$$$.

A Ranom number is a sequence of Ranom digits. The value of the Ranom number is calculated as follows: the values of all digits are summed up, but some digits are taken with negative signs: a digit is taken with negative sign if there is a digit with a strictly greater value to the right of it (not necessarily immediately after it); otherwise, that digit is taken with a positive sign.

For example, the value of the Ranom number DAAABDCA is $$$1000 - 1 - 1 - 1 - 10 + 1000 + 100 + 1 = 2088$$$.

You are given a Ranom number. You can change no more than one digit in it. Calculate the maximum possible value of the resulting number.

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

The only line of each test case contains a string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) consisting of uppercase Latin letters from A to E — the Ranom number you are given.

The sum of the string lengths over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the maximum possible value of the number, if you can change no more than one digit in it.

## Examples
```input
4
DAAABDCA
AB
ABCDEEDCBA
DDDDAAADDABECD
```
```output
11088
10010
31000
15886
```

## Note
In the first example, you can get EAAABDCA with the value $$$10000-1-1-1-10+1000+100+1=11088$$$.

In the second example, you can get EB with the value $$$10000+10=10010$$$.

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
There is a square matrix, consisting of $$$n$$$ rows and $$$n$$$ columns of cells, both numbered from $$$1$$$ to $$$n$$$. The cells are colored white or black. Cells from $$$1$$$ to $$$a_i$$$ are black, and cells from $$$a_i+1$$$ to $$$n$$$ are white, in the $$$i$$$-th column.

You want to place $$$m$$$ integers in the matrix, from $$$1$$$ to $$$m$$$. There are two rules:

- each cell should contain at most one integer;
- black cells should not contain integers.

The beauty of the matrix is the number of such $$$j$$$ that $$$j+1$$$ is written in the same row, in the next column as $$$j$$$ (in the neighbouring cell to the right).

What's the maximum possible beauty of the matrix?

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

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the matrix.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — the number of black cells in each column.

The third line contains a single integer $$$m$$$ ($$$0 \le m \le \sum \limits_{i=1}^n n - a_i$$$) — the number of integers you have to write in the matrix. Note that this number might not fit into a 32-bit integer data type.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the maximum beauty of the matrix after you write all $$$m$$$ integers in it. Note that there are no more integers than the white cells, so the answer always exists.

## Examples
```input
6
3
0 0 0
9
4
2 0 3 1
5
4
2 0 3 1
6
4
2 0 3 1
10
10
0 2 2 1 5 10 3 4 1 1
20
1
1
0
```
```output
6
3
4
4
16
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: 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 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
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 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
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.