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

# Problem
You are given a sequence $$$a_1, a_2, \ldots, a_n$$$ of non-negative integers.

You need to find the largest number $$$m$$$ of triples $$$(i_1, j_1, k_1)$$$, $$$(i_2, j_2, k_2)$$$, ..., $$$(i_m, j_m, k_m)$$$ such that:

- $$$1 \leq i_p < j_p < k_p \leq n$$$ for each $$$p$$$ in $$$1, 2, \ldots, m$$$;
- $$$a_{i_p} = a_{k_p} = 0$$$, $$$a_{j_p} \neq 0$$$;
- all $$$a_{j_1}, a_{j_2}, \ldots, a_{j_m}$$$ are different;
- all $$$i_1, j_1, k_1, i_2, j_2, k_2, \ldots, i_m, j_m, k_m$$$ are different.

## Input Format
The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 500\,000$$$): the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 500\,000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$).

The total sum of $$$n$$$ is at most $$$500\,000$$$.

## Output Format
For each test case, print one integer $$$m$$$: the largest number of proper triples that you can find.

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

## Note
In the first two test cases, there are not enough elements even for a single triple, so the answer is $$$0$$$.

In the third test case we can select one triple $$$(1, 2, 3)$$$.

In the fourth test case we can select two triples $$$(1, 3, 5)$$$ and $$$(2, 4, 6)$$$.

In the fifth test case we can select one triple $$$(1, 2, 3)$$$. We can't select two triples $$$(1, 2, 3)$$$ and $$$(4, 5, 6)$$$, because $$$a_2 = a_5$$$.

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

# Problem
You are given a positive integer $$$k$$$ and an array $$$a_1, a_2, \ldots, a_n$$$ of non-negative distinct integers not smaller than $$$k$$$ and not greater than $$$2^c-1$$$.

In each of the next $$$k$$$ seconds, one element is chosen randomly equiprobably out of all $$$n$$$ elements and decreased by $$$1$$$.

For each integer $$$x$$$, $$$0 \leq x \leq 2^c - 1$$$, you need to find the probability that in the end the bitwise XOR of all elements of the array is equal to $$$x$$$.

Each of these values can be represented as an irreducible fraction $$$\frac{p}{q}$$$, and you need to find the value of $$$p \cdot q^{-1}$$$ modulo $$$998\,244\,353$$$.

## Input Format
The first line of input contains three integers $$$n, k, c$$$ ($$$1 \leq n \leq (2^c - k)$$$, $$$1 \leq k \leq 16$$$, $$$1 \leq c \leq 16$$$).

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$k \leq a_i \leq 2^c-1$$$).

## Output Format
Print $$$2^c$$$ integers: the probability that the bitwise XOR is equal to $$$x$$$ in the end for $$$x$$$ in $$$\{0, 1, \ldots, 2^c-1\}$$$ modulo $$$998\,244\,353$$$.

## Examples
```input
4 1 3
1 2 3 4
```
```output
0 0 0 748683265 0 499122177 0 748683265
```

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
In order to celebrate Twice's 5th anniversary, Tzuyu and Sana decided to play a game.

Tzuyu gave Sana two integers $$$a$$$ and $$$b$$$ and a really important quest.

In order to complete the quest, Sana has to output the smallest possible value of ($$$a \oplus x$$$) + ($$$b \oplus x$$$) for any given $$$x$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

## 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 only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^{9}$$$).

## Output Format
For each testcase, output the smallest possible value of the given expression.

## Examples
```input
6
6 12
4 9
59 832
28 14
4925 2912
1 1
```
```output
10
13
891
18
6237
0
```

## Note
For the first test case Sana can choose $$$x=4$$$ and the value will be ($$$6 \oplus 4$$$) + ($$$12 \oplus 4$$$) = $$$2 + 8$$$ = $$$10$$$. It can be shown that this is the smallest possible value.

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
Ringo found a string $$$s$$$ of length $$$n$$$ in his yellow submarine. The string contains only lowercase letters from the English alphabet. As Ringo and his friends love palindromes, he would like to turn the string $$$s$$$ into a palindrome by applying two types of operations to the string.

The first operation allows him to choose $$$i$$$ ($$$2 \le i \le n-1$$$) and to append the substring $$$s_2s_3 \ldots s_i$$$ ($$$i - 1$$$ characters) reversed to the front of $$$s$$$.

The second operation allows him to choose $$$i$$$ ($$$2 \le i \le n-1$$$) and to append the substring $$$s_i s_{i + 1}\ldots s_{n - 1}$$$ ($$$n - i$$$ characters) reversed to the end of $$$s$$$.

Note that characters in the string in this problem are indexed from $$$1$$$.

For example suppose $$$s=$$$abcdef. If he performs the first operation with $$$i=3$$$ then he appends cb to the front of $$$s$$$ and the result will be cbabcdef. Performing the second operation on the resulted string with $$$i=5$$$ will yield cbabcdefedc.

Your task is to help Ringo make the entire string a palindrome by applying any of the two operations (in total) at most $$$30$$$ times. The length of the resulting palindrome must not exceed $$$10^6$$$

It is guaranteed that under these constraints there always is a solution. Also note you do not have to minimize neither the number of operations applied, nor the length of the resulting string, but they have to fit into the constraints.

## Input Format
The only line contains the string $$$S$$$ ($$$3 \le |s| \le 10^5$$$) of lowercase letters from the English alphabet.

## Output Format
The first line should contain $$$k$$$ ($$$0\le k \le 30$$$)  — the number of operations performed.

Each of the following $$$k$$$ lines should describe an operation in form L i or R i. $$$L$$$ represents the first operation, $$$R$$$ represents the second operation, $$$i$$$ represents the index chosen.

The length of the resulting palindrome must not exceed $$$10^6$$$.

## Examples
```input
abac
```
```output
2
R 2
R 5
```
-----
```input
acccc
```
```output
2
L 4
L 2
```
-----
```input
hannah
```
```output
0
```

## Note
For the first example the following operations are performed:

abac $$$\to$$$ abacab $$$\to$$$ abacaba

The second sample performs the following operations: acccc $$$\to$$$ cccacccc $$$\to$$$ ccccacccc

The third example is already a palindrome so no operations are required.

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
Lindsey Buckingham told Stevie Nicks "Go your own way". Nicks is now sad and wants to go away as quickly as possible, but she lives in a 2D hexagonal world.

Consider a hexagonal tiling of the plane as on the picture below.

Nicks wishes to go from the cell marked $$$(0, 0)$$$ to a certain cell given by the coordinates. She may go from a hexagon to any of its six neighbors you want, but there is a cost associated with each of them. The costs depend only on the direction in which you travel. Going from $$$(0, 0)$$$ to $$$(1, 1)$$$ will take the exact same cost as going from $$$(-2, -1)$$$ to $$$(-1, 0)$$$. The costs are given in the input in the order $$$c_1$$$, $$$c_2$$$, $$$c_3$$$, $$$c_4$$$, $$$c_5$$$, $$$c_6$$$ as in the picture below.

Print the smallest cost of a path from the origin which has coordinates $$$(0, 0)$$$ to the given cell.

## 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 two integers $$$x$$$ and $$$y$$$ ($$$-10^{9} \le x, y \le 10^{9}$$$) representing the coordinates of the target hexagon.

The second line of each test case contains six integers $$$c_1$$$, $$$c_2$$$, $$$c_3$$$, $$$c_4$$$, $$$c_5$$$, $$$c_6$$$ ($$$1 \le c_1, c_2, c_3, c_4, c_5, c_6 \le 10^{9}$$$) representing the six costs of the making one step in a particular direction (refer to the picture above to see which edge is for each value).

## Output Format
For each testcase output the smallest cost of a path from the origin to the given cell.

## Examples
```input
2
-3 1
1 3 5 7 9 11
1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
```
```output
18
1000000000000000000
```

## Note
The picture below shows the solution for the first sample. The cost $$$18$$$ is reached by taking $$$c_3$$$ 3 times and $$$c_2$$$ once, amounting to $$$5+5+5+3=18$$$.

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
While playing yet another strategy game, Mans has recruited $$$n$$$ Swedish heroes, whose powers which can be represented as an array $$$a$$$.

Unfortunately, not all of those mighty heroes were created as capable as he wanted, so that he decided to do something about it. In order to accomplish his goal, he can pick two consecutive heroes, with powers $$$a_i$$$ and $$$a_{i+1}$$$, remove them and insert a hero with power $$$-(a_i+a_{i+1})$$$ back in the same position.

For example if the array contains the elements $$$[5, 6, 7, 8]$$$, he can pick $$$6$$$ and $$$7$$$ and get $$$[5, -(6+7), 8] = [5, -13, 8]$$$.

After he will perform this operation $$$n-1$$$ times, Mans will end up having only one hero. He wants his power to be as big as possible. What's the largest possible power he can achieve?

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 200000$$$).

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

## Output Format
Print the largest possible power he can achieve after $$$n-1$$$ operations.

## Examples
```input
4
5 6 7 8
```
```output
26
```
-----
```input
5
4 -5 9 -2 1
```
```output
15
```

## Note
Suitable list of operations for the first sample:

$$$[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$$$

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
Bertown is a city with $$$n$$$ buildings in a straight line.

The city's security service discovered that some buildings were mined. A map was compiled, which is a string of length $$$n$$$, where the $$$i$$$-th character is "1" if there is a mine under the building number $$$i$$$ and "0" otherwise.

Bertown's best sapper knows how to activate mines so that the buildings above them are not damaged. When a mine under the building numbered $$$x$$$ is activated, it explodes and activates two adjacent mines under the buildings numbered $$$x-1$$$ and $$$x+1$$$ (if there were no mines under the building, then nothing happens). Thus, it is enough to activate any one mine on a continuous segment of mines to activate all the mines of this segment. For manual activation of one mine, the sapper takes $$$a$$$ coins. He can repeat this operation as many times as you want.

Also, a sapper can place a mine under a building if it wasn't there. For such an operation, he takes $$$b$$$ coins. He can also repeat this operation as many times as you want.

The sapper can carry out operations in any order.

You want to blow up all the mines in the city to make it safe. Find the minimum number of coins that the sapper will have to pay so that after his actions there are no mines left in the city.

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

Each test case begins with a line containing two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 1000$$$) — the cost of activating and placing one mine, respectively.

The next line contains a map of mines in the city — a string consisting of zeros and ones.

The sum of the string lengths for all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output one integer — the minimum number of coins that the sapper will have to pay.

## Examples
```input
2
1 1
01000010
5 1
01101110
```
```output
2
6
```

## Note
In the second test case, if we place a mine under the fourth building and then activate it, then all mines on the field are activated. The cost of such operations is six, $$$b=1$$$ coin for placing a mine and $$$a=5$$$ coins for activating.

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
Argus was charged with guarding Io, which is not an ordinary cow. Io is quite an explorer, and she wanders off rather frequently, making Argus' life stressful. So the cowherd decided to construct an enclosed pasture for Io.

There are $$$n$$$ trees growing along the river, where Argus tends Io. For this problem, the river can be viewed as the $$$OX$$$ axis of the Cartesian coordinate system, and the $$$n$$$ trees as points with the $$$y$$$-coordinate equal $$$0$$$. There is also another tree growing in the point $$$(0, 1)$$$.

Argus will tie a rope around three of the trees, creating a triangular pasture. Its exact shape doesn't matter to Io, but its area is crucial to her. There may be many ways for Argus to arrange the fence, but only the ones which result in different areas of the pasture are interesting for Io. Calculate the number of different areas that her pasture may have. Note that the pasture must have nonzero area.

## 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. Then $$$t$$$ test cases follow, each one is described in two lines.

In the first line of each test case there is a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) denoting the number of trees growing along the river. Next line contains $$$n$$$ distinct integers $$$x_1 < x_2 < \ldots < x_{n - 1} < x_n$$$ ($$$1 \leq x_i \leq 50$$$), the $$$x$$$-coordinates of trees growing along the river.

## Output Format
In a single line output an integer, the number of different nonzero areas that triangles with trees as vertices may have.

## Examples
```input
8
4
1 2 4 5
3
1 3 5
3
2 6 8
2
1 2
1
50
5
3 4 5 6 8
3
1 25 26
6
1 2 4 8 16 32
```
```output
4
2
3
1
0
5
3
15
```

## Note
In the first test case, we have $$$6$$$ non-degenerate triangles with the following areas: $$$0.5$$$, $$$0.5$$$, $$$1$$$, $$$1.5$$$, $$$1.5$$$ and $$$2$$$. The pasture can have $$$4$$$ different areas, and thus $$$4$$$ is the answer.

In the second test case, we have $$$3$$$ non-degenerate triangles with the following areas: $$$1$$$, $$$1$$$ and $$$2$$$. The pasture can have $$$2$$$ different areas, so $$$2$$$ is the answer.

The following two drawings present the situation in the second test case. The blue triangles in the first drawing have area $$$1$$$. The red triangle in the second drawing has area $$$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
After his wife's tragic death, Eurydice, Orpheus descended to the realm of death to see her. Reaching its gates was uneasy, but passing through them proved to be even more challenging. Mostly because of Cerberus, the three-headed hound of Hades.

Orpheus, a famous poet, and musician plans to calm Cerberus with his poetry and safely walk past him. He created a very peculiar poem for Cerberus. It consists only of lowercase English letters.

We call a poem's substring a palindrome if and only if it reads the same backwards and forwards. A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.

Unfortunately, Cerberus dislikes palindromes of length greater than $$$1$$$. For example in the poem abaa the hound of Hades wouldn't like substrings aba and aa.

Orpheus can only calm Cerberus if the hound likes his poetry. That's why he wants to change his poem so that it does not contain any palindrome substrings of length greater than $$$1$$$.

Orpheus can modify the poem by replacing a letter at any position with any lowercase English letter. He can use this operation arbitrarily many times (possibly zero). Since there can be many palindromes in his poem, he may have to make some corrections. But how many, exactly? Given the poem, determine the minimal number of letters that have to be changed so that the poem does not contain any palindromes of length greater than $$$1$$$.

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

The first and only line of each test case contains a non-empty string of lowercase English letters, Orpheus' poem.

The sum of the length of Orpheus' poems in all test cases will not exceed $$$10^5$$$.

## Output Format
You should output $$$t$$$ lines, $$$i$$$-th line should contain a single integer, answer to the $$$i$$$-th test case.

## Examples
```input
7
babba
abaac
codeforces
zeroorez
abcdcba
bbbbbbb
a
```
```output
1
1
0
1
1
4
0
```

## Note
In the first test case, we can replace the third character with c and obtain a palindrome-less poem bacba.

In the second test case, we can replace the third character with d and obtain a palindrome-less poem abdac.

In the third test case, the initial poem already doesn't contain any palindromes, so Orpheus doesn't need to change anything there.

Now solve the problem and return the code.