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 an array $$$a$$$ with $$$n-1$$$ integers. Let $$$x$$$ be the bitwise XOR of all elements of the array. The number $$$x$$$ is added to the end of the array $$$a$$$ (now it has length $$$n$$$), and then the elements are shuffled.

You are given the newly formed array $$$a$$$. What is $$$x$$$? If there are multiple possible values of $$$x$$$, you can output any of them.

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

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of integers in the resulting array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 127$$$) — the elements of the newly formed array $$$a$$$.

Additional constraint on the input: the array $$$a$$$ is made by the process described in the statement; that is, some value of $$$x$$$ exists.

## Output Format
For each test case, output a single integer — the value of $$$x$$$, as described in the statement. If there are multiple possible values of $$$x$$$, output any of them.

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

## Note
In the first test case, one possible array $$$a$$$ is $$$a=[2, 5, 4]$$$. Then $$$x = 2 \oplus 5 \oplus 4 = 3$$$ ($$$\oplus$$$ denotes the bitwise XOR), so the new array is $$$[2, 5, 4, 3]$$$. Afterwards, the array is shuffled to form $$$[4, 3, 2, 5]$$$.

In the second test case, one possible array $$$a$$$ is $$$a=[1, 10, 6, 10]$$$. Then $$$x = 1 \oplus 10 \oplus 6 \oplus 10 = 7$$$, so the new array is $$$[1, 10, 6, 10, 7]$$$. Afterwards, the array is shuffled to form $$$[6, 1, 10, 7, 10]$$$.

In the third test case, all elements of the array are equal to $$$6$$$, so $$$x=6$$$.

In the fourth test case, one possible array $$$a$$$ is $$$a=[100, 100]$$$. Then $$$x = 100 \oplus 100 = 0$$$, so the new array is $$$[100, 100, 0]$$$. Afterwards, the array is shuffled to form $$$[100, 100, 0]$$$. (Note that after the shuffle, the array can remain the same.)

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 are $$$n$$$ piles of sand where the $$$i$$$-th pile has $$$a_i$$$ blocks of sand. The $$$i$$$-th pile is called too tall if $$$1 < i < n$$$ and $$$a_i > a_{i-1} + a_{i+1}$$$. That is, a pile is too tall if it has more sand than its two neighbours combined. (Note that piles on the ends of the array cannot be too tall.)

You are given an integer $$$k$$$. An operation consists of picking $$$k$$$ consecutive piles of sand and adding one unit of sand to them all. Formally, pick $$$1 \leq l,r \leq n$$$ such that $$$r-l+1=k$$$. Then for all $$$l \leq i \leq r$$$, update $$$a_i \gets a_i+1$$$.

What is the maximum number of piles that can simultaneously be too tall after some (possibly zero) operations?

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq k \leq n$$$) — the number of piles of sand and the size of the operation, respectively.

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

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 a single integer — the maximum number of piles that are simultaneously too tall after some (possibly zero) operations.

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

## Note
In the first test case, we can perform the following three operations:

- Add one unit of sand to piles $$$1$$$ and $$$2$$$: $$$[\color{red}{3}, \color{red}{10}, 2, 4, 1]$$$.
- Add one unit of sand to piles $$$4$$$ and $$$5$$$: $$$[3, 10, 2, \color{red}{5}, \color{red}{2}]$$$.
- Add one unit of sand to piles $$$3$$$ and $$$4$$$: $$$[3, 10, \color{red}{3}, \color{red}{6}, 2]$$$.

In the second test case, any operation will increase all piles by $$$1$$$ unit, so the number of too tall piles will always be $$$0$$$.

In the third test case, we can increase any pile by $$$1$$$ unit of sand. It can be shown that the maximum number of too tall piles is $$$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
You are given an array $$$a$$$ of length $$$n$$$. The array is called 3SUM-closed if for all distinct indices $$$i$$$, $$$j$$$, $$$k$$$, the sum $$$a_i + a_j + a_k$$$ is an element of the array. More formally, $$$a$$$ is 3SUM-closed if for all integers $$$1 \leq i < j < k \leq n$$$, there exists some integer $$$1 \leq l \leq n$$$ such that $$$a_i + a_j + a_k = a_l$$$.

Determine if $$$a$$$ is 3SUM-closed.

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

The first line of each test case contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — the elements of the array.

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

## Output Format
For each test case, output "YES" (without quotes) if $$$a$$$ is 3SUM-closed and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

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

## Note
In the first test case, there is only one triple where $$$i=1$$$, $$$j=2$$$, $$$k=3$$$. In this case, $$$a_1 + a_2 + a_3 = 0$$$, which is an element of the array ($$$a_2 = 0$$$), so the array is 3SUM-closed.

In the second test case, $$$a_1 + a_4 + a_5 = -1$$$, which is not an element of the array. Therefore, the array is not 3SUM-closed.

In the third test case, $$$a_i + a_j + a_k = 0$$$ for all distinct $$$i$$$, $$$j$$$, $$$k$$$, and $$$0$$$ is an element of the array, so the array is 3SUM-closed.

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 binary string $$$t$$$ of length $$$10^{100}$$$, and initally all of its bits are $$$\texttt{0}$$$. You are given a binary string $$$s$$$, and perform the following operation some times:

- Select some substring of $$$t$$$, and replace it with its XOR with $$$s$$$.$$$^\dagger$$$

Find the lexicographically largest$$$^\ddagger$$$ string $$$t$$$ satisfying these constraints, or report that no such string exists.

$$$^\dagger$$$ Formally, choose an index $$$i$$$ such that $$$0 \leq i \leq 10^{100}-|s|$$$. For all $$$1 \leq j \leq |s|$$$, if $$$s_j = \texttt{1}$$$, then toggle $$$t_{i+j}$$$. That is, if $$$t_{i+j}=\texttt{0}$$$, set $$$t_{i+j}=\texttt{1}$$$. Otherwise if $$$t_{i+j}=\texttt{1}$$$, set $$$t_{i+j}=\texttt{0}$$$.

$$$^\ddagger$$$ A binary string $$$a$$$ is lexicographically larger than a binary string $$$b$$$ of the same length if in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a bit $$$\texttt{1}$$$ and the corresponding bit in $$$b$$$ is $$$\texttt{0}$$$.

## Input Format
The only line of each test contains a single binary string $$$s$$$ ($$$1 \leq |s| \leq 35$$$).

## Output Format
If no string $$$t$$$ exists as described in the statement, output -1. Otherwise, output the integers $$$p$$$ and $$$q$$$ ($$$1 \leq p < q \leq 10^{100}$$$) such that the $$$p$$$-th and $$$q$$$-th bits of the lexicographically maximal $$$t$$$ are $$$\texttt{1}$$$.

## Examples
```input
1
```
```output
1 2
```
-----
```input
001
```
```output
3 4
```
-----
```input
1111
```
```output
1 5
```
-----
```input
00000
```
```output
-1
```
-----
```input
00000111110000011111000001111101010
```
```output
6 37452687
```

## Note
In the first test, you can perform the following operations. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{1}}\texttt{0000}\ldots \to \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots$$$$$$

In the second test, you can perform the following operations. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{001}}\texttt{00}\ldots \to \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots$$$$$$

In the third test, you can perform the following operations. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{1111}}\texttt{0}\ldots \to \texttt{1}\color{red}{\texttt{0001}}\ldots$$$$$$

It can be proven that these strings $$$t$$$ are the lexicographically largest ones.

In the fourth test, you can't make a single bit $$$\texttt{1}$$$, so it is impossible.

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

# Problem
Nick is interested in prime numbers. Once he read about Goldbach problem. It states that every even integer greater than 2 can be expressed as the sum of two primes. That got Nick's attention and he decided to invent a problem of his own and call it Noldbach problem. Since Nick is interested only in prime numbers, Noldbach problem states that at least k prime numbers from 2 to n inclusively can be expressed as the sum of three integer numbers: two neighboring prime numbers and 1. For example, 19 = 7 + 11 + 1, or 13 = 5 + 7 + 1.

Two prime numbers are called neighboring if there are no other prime numbers between them.

You are to help Nick, and find out if he is right or wrong.

## Input Format
The first line of the input contains two integers n (2 ≤ n ≤ 1000) and k (0 ≤ k ≤ 1000).

## Output Format
Output YES if at least k prime numbers from 2 to n inclusively can be expressed as it was described above. Otherwise output NO.

## Examples
```input
27 2
```
```output
YES
```
-----
```input
45 7
```
```output
NO
```

## Note
In the first sample the answer is YES since at least two numbers can be expressed as it was described (for example, 13 and 19). In the second sample the answer is NO since it is impossible to express 7 prime numbers from 2 to 45 in the desired form.

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

# Problem
Nick's company employed n people. Now Nick needs to build a tree hierarchy of «supervisor-surbodinate» relations in the company (this is to say that each employee, except one, has exactly one supervisor). There are m applications written in the following form: «employee ai is ready to become a supervisor of employee bi at extra cost ci». The qualification qj of each employee is known, and for each application the following is true: qai > qbi.

Would you help Nick calculate the minimum cost of such a hierarchy, or find out that it is impossible to build it.

## Input Format
The first input line contains integer n (1 ≤ n ≤ 1000) — amount of employees in the company. The following line contains n space-separated numbers qj (0 ≤ qj ≤ 106)— the employees' qualifications. The following line contains number m (0 ≤ m ≤ 10000) — amount of received applications. The following m lines contain the applications themselves, each of them in the form of three space-separated numbers: ai, bi and ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 106). Different applications can be similar, i.e. they can come from one and the same employee who offered to become a supervisor of the same person but at a different cost. For each application qai > qbi.

## Output Format
Output the only line — the minimum cost of building such a hierarchy, or -1 if it is impossible to build it.

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

## Note
In the first sample one of the possible ways for building a hierarchy is to take applications with indexes 1, 2 and 4, which give 11 as the minimum total cost. In the second sample it is impossible to build the required hierarchy, so the answer is -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: 3.0 seconds
Memory limit: 128.0 MB

# Problem
Nick likes strings very much, he likes to rotate them, sort them, rearrange characters within a string... Once he wrote a random string of characters a, b, c on a piece of paper and began to perform the following operations:

- to take two adjacent characters and replace the second character with the first one,
- to take two adjacent characters and replace the first character with the second one

To understand these actions better, let's take a look at a string «abc». All of the following strings can be obtained by performing one of the described operations on «abc»: «bbc», «abb», «acc». Let's denote the frequency of a character for each of the characters a, b and c as the number of occurrences of this character in the string. For example, for string «abc»: |a| = 1, |b| = 1, |c| = 1, and for string «bbc»: |a| = 0, |b| = 2, |c| = 1.

While performing the described operations, Nick sometimes got balanced strings. Let's say that a string is balanced, if the frequencies of each character differ by at most 1. That is  - 1 ≤ |a| - |b| ≤ 1,  - 1 ≤ |a| - |c| ≤ 1 и  - 1 ≤ |b| - |c| ≤ 1.

Would you help Nick find the number of different balanced strings that can be obtained by performing the operations described above, perhaps multiple times, on the given string s. This number should be calculated modulo 51123987.

## Input Format
The first line contains integer n (1 ≤ n ≤ 150) — the length of the given string s. Next line contains the given string s. The initial string can be balanced as well, in this case it should be counted too. The given string s consists only of characters a, b and c.

## Output Format
Output the only number — the number of different balanced strings that can be obtained by performing the described operations, perhaps multiple times, on the given string s, modulo 51123987.

## Examples
```input
4
abca
```
```output
7
```
-----
```input
4
abbc
```
```output
3
```
-----
```input
2
ab
```
```output
1
```

## Note
In the first sample it is possible to get 51 different strings through the described operations, but only 7 of them are balanced: «abca», «bbca», «bcca», «bcaa», «abcc», «abbc», «aabc». In the second sample: «abbc», «aabc», «abcc». In the third sample there is only one balanced string — «ab» itself.

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

# Problem
Nick is attracted by everything unconventional. He doesn't like decimal number system any more, and he decided to study other number systems. A number system with base b caught his attention. Before he starts studying it, he wants to write in his notepad all the numbers of length n without leading zeros in this number system. Each page in Nick's notepad has enough space for c numbers exactly. Nick writes every suitable number only once, starting with the first clean page and leaving no clean spaces. Nick never writes number 0 as he has unpleasant memories about zero divide.

Would you help Nick find out how many numbers will be written on the last page.

## Input Format
The only input line contains three space-separated integers b, n and c (2 ≤ b < 10106, 1 ≤ n < 10106, 1 ≤ c ≤ 109). You may consider that Nick has infinite patience, endless amount of paper and representations of digits as characters. The numbers doesn't contain leading zeros.

## Output Format
In the only line output the amount of numbers written on the same page as the last number.

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

## Note
In both samples there are exactly 4 numbers of length 3 in binary number system. In the first sample Nick writes 3 numbers on the first page and 1 on the second page. In the second sample all the 4 numbers can be written on the first page.

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

# Problem
In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.

Let's look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:

• «b» — 1..1

• «bab» — 1..3

• «a» — 2..2

• «b» — 3..3

• «bb» — 3..4

• «b» — 4..4

Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:

1. 1..1 cross with 1..3

2. 1..3 cross with 2..2

3. 1..3 cross with 3..3

4. 1..3 cross with 3..4

5. 3..3 cross with 3..4

6. 3..4 cross with 4..4

Since it's very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.

## Input Format
The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from a to z).

## Output Format
In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.

## Examples
```input
4
babb
```
```output
6
```
-----
```input
2
aa
```
```output
2
```

Now solve the problem and return the code.