apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a binary string$$$^{\dagger}$$$. Please find the minimum number of pieces you need to cut it into, so that the resulting pieces can be rearranged into a sorted binary string.

Note that:

- each character must lie in exactly one of the pieces;
- the pieces must be contiguous substrings of the original string;
- you must use all the pieces in the rearrangement.

$$$^{\dagger}$$$ A binary string is a string consisting of characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$. A sorted binary string is a binary string such that all characters $$$\texttt{0}$$$ come before all characters $$$\texttt{1}$$$.

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

The only line of each test case contains a single string $$$s$$$ ($$$1 \leq |s| \leq 500$$$) consisting of characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$, where $$$|s|$$$ denotes the length of the string $$$s$$$.

## Output Format
For each test case, output a single integer — the minimum number of pieces needed to be able to rearrange the string into a sorted binary string.

## Examples
```input
6
11010
00000000
1
10
0001111
0110
```
```output
3
1
1
2
1
2
```

## Note
The first test case is pictured in the statement. It can be proven that you can't use fewer than $$$3$$$ pieces.

In the second and third test cases, the binary string is already sorted, so only $$$1$$$ piece is needed.

In the fourth test case, you need to make a single cut between the two characters and rearrange them to make the string $$$\texttt{01}$$$.

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
Given an integer $$$r$$$, find the number of lattice points that have a Euclidean distance from $$$(0, 0)$$$ greater than or equal to $$$r$$$ but strictly less than $$$r+1$$$.

A lattice point is a point with integer coordinates. The Euclidean distance from $$$(0, 0)$$$ to the point $$$(x,y)$$$ is $$$\sqrt{x^2 + y^2}$$$.

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

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

The sum of $$$r$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output a single integer — the number of lattice points that have an Euclidean distance $$$d$$$ from $$$(0, 0)$$$ such that $$$r \leq d < r+1$$$.

## Examples
```input
6
1
2
3
4
5
1984
```
```output
8
16
20
24
40
12504
```

## Note
The points for the first three test cases are shown below.

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 are given an array $$$a$$$ consisting of $$$n$$$ nonnegative integers.

You can swap the elements at positions $$$i$$$ and $$$j$$$ if $$$a_i~\mathsf{XOR}~a_j < 4$$$, where $$$\mathsf{XOR}$$$ is the bitwise XOR operation.

Find the lexicographically smallest array that can be made with any number of swaps.

An array $$$x$$$ is lexicographically smaller than an array $$$y$$$ if in the first position where $$$x$$$ and $$$y$$$ differ, $$$x_i < y_i$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the array.

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

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 — the lexicographically smallest array that can be made with any number of swaps.

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

## Note
For the first test case, you can swap any two elements, so we can produce the sorted array.

For the second test case, you can swap $$$2$$$ and $$$1$$$ (their $$$\mathsf{XOR}$$$ is $$$3$$$), $$$7$$$ and $$$5$$$ (their $$$\mathsf{XOR}$$$ is $$$2$$$), and $$$7$$$ and $$$6$$$ (their $$$\mathsf{XOR}$$$ is $$$1$$$) to get the lexicographically smallest array.

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
Vlad is planning to hold $$$m$$$ rounds next month. Each round should contain one problem of difficulty levels 'A', 'B', 'C', 'D', 'E', 'F', and 'G'.

Vlad already has a bank of $$$n$$$ problems, where the $$$i$$$-th problem has a difficulty level of $$$a_i$$$. There may not be enough of these problems, so he may have to come up with a few more problems.

Vlad wants to come up with as few problems as possible, so he asks you to find the minimum number of problems he needs to come up with in order to hold $$$m$$$ rounds.

For example, if $$$m=1$$$, $$$n = 10$$$, $$$a=$$$ 'BGECDCBDED', then he needs to come up with two problems: one of difficulty level 'A' and one of difficulty level 'F'.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 50$$$, $$$1 \le m \le 5$$$) — the number of problems in the bank and the number of upcoming rounds, respectively.

The second line of each test case contains a string $$$a$$$ of $$$n$$$ characters from 'A' to 'G' — the difficulties of the problems in the bank.

## Output Format
For each test case, output a single integer — the minimum number of problems that need to come up with to hold $$$m$$$ rounds.

## Examples
```input
3
10 1
BGECDCBDED
10 2
BGECDCBDED
9 1
BBCDEFFGG
```
```output
2
5
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
Dmitry has $$$n$$$ cubes, numbered from left to right from $$$1$$$ to $$$n$$$. The cube with index $$$f$$$ is his favorite.

Dmitry threw all the cubes on the table, and the $$$i$$$-th cube showed the value $$$a_i$$$ ($$$1 \le a_i \le 100$$$). After that, he arranged the cubes in non-increasing order of their values, from largest to smallest. If two cubes show the same value, they can go in any order.

After sorting, Dmitry removed the first $$$k$$$ cubes. Then he became interested in whether he removed his favorite cube (note that its position could have changed after sorting).

For example, if $$$n=5$$$, $$$f=2$$$, $$$a = [4, \color{green}3, 3, 2, 3]$$$ (the favorite cube is highlighted in green), and $$$k = 2$$$, the following could have happened:

- After sorting $$$a=[4, \color{green}3, 3, 3, 2]$$$, since the favorite cube ended up in the second position, it will be removed.
- After sorting $$$a=[4, 3, \color{green}3, 3, 2]$$$, since the favorite cube ended up in the third position, it will not be removed.

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

The first line of each test case description contains three integers $$$n$$$, $$$f$$$, and $$$k$$$ ($$$1 \le f, k \le n \le 100$$$) — the number of cubes, the index of Dmitry's favorite cube, and the number of removed cubes, respectively.

The second line of each test case description contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 100$$$) — the values shown on the cubes.

## Output Format
For each test case, output one line — "YES" if the cube will be removed in all cases, "NO" if it will not be removed in any case, "MAYBE" if it may be either removed or left.

You can output the answer in any case. For example, the strings "YES", "nO", "mAyBe" will be accepted as answers.

## Examples
```input
12
5 2 2
4 3 3 2 3
5 5 3
4 2 1 3 5
5 5 2
5 2 4 1 3
5 5 5
1 2 5 4 3
5 5 4
3 1 2 4 5
5 5 5
4 3 2 1 5
6 5 3
1 2 3 1 2 3
10 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1
42
5 2 3
2 2 1 1 2
2 1 1
2 1
5 3 1
3 3 2 3 2
```
```output
MAYBE
YES
NO
YES
YES
YES
MAYBE
MAYBE
YES
YES
YES
NO
```

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
Define the range of a non-empty array to be the maximum value minus the minimum value. For example, the range of $$$[1,4,2]$$$ is $$$4-1=3$$$.

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n \geq 3$$$. It is guaranteed $$$a$$$ is sorted.

You have to color each element of $$$a$$$ red or blue so that:

- the range of the red elements does not equal the range of the blue elements, and
- there is at least one element of each color.

If there does not exist any such coloring, you should report it. If there are multiple valid colorings, you can print any of them.

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

The first line of each test case contains an integer $$$n$$$ ($$$3 \leq n \leq 50$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$). It is guaranteed $$$a_1 \leq a_2 \leq \ldots \leq a_{n - 1} \leq a_{n}$$$.

## Output Format
For each test case, if it is impossible to color $$$a$$$ to satisfy all the constraints, output $$$\texttt{NO}$$$.

Otherwise, first output $$$\texttt{YES}$$$.

Then, output a string $$$s$$$ of length $$$n$$$. For $$$1 \leq i \leq n$$$, if you color $$$a_i$$$ red, $$$s_i$$$ should be $$$\texttt{R}$$$. For $$$1 \leq i \leq n$$$, if you color $$$a_i$$$ blue, $$$s_i$$$ should be $$$\texttt{B}$$$.

## Examples
```input
7
4
1 1 2 2
5
1 2 3 4 5
3
3 3 3
4
1 2 2 2
3
1 2 2
3
1 1 2
3
1 9 84
```
```output
YES
RBRR
YES
BBRBB
NO
YES
RBBR
YES
RRB
YES
BRR
YES
BRB
```

## Note
In the first test case, given the array $$$[1, 1, 2, 2]$$$, we can color the second element blue and the remaining elements red; then the range of the red elements $$$[1, 2, 2]$$$ is $$$2-1=1$$$, and the range of the blue elements $$$[1]$$$ is $$$1-1=0$$$.

In the second test case, we can color the first, second, fourth and fifth elements $$$[1, 2, 4, 5]$$$ blue and the remaining elements $$$[3]$$$ red.

The range of the red elements is $$$3 - 3 = 0$$$ and the range of the blue elements is $$$5 - 1 = 4$$$, which are different.

In the third test case, it can be shown there is no way to color $$$a = [3, 3, 3]$$$ to satisfy the constraints.

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
A digit is large if it is between $$$5$$$ and $$$9$$$, inclusive. A positive integer is large if all of its digits are large.

You are given an integer $$$x$$$. Can it be the sum of two large positive integers with the same number of digits?

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

The only line of each test case contains a single integer $$$x$$$ ($$$10 \leq x \leq 10^{18}$$$).

## Output Format
For each test case, output $$$\texttt{YES}$$$ if $$$x$$$ satisfies the condition, and $$$\texttt{NO}$$$ otherwise.

You can output $$$\texttt{YES}$$$ and $$$\texttt{NO}$$$ in any case (for example, strings $$$\texttt{yES}$$$, $$$\texttt{yes}$$$, and $$$\texttt{Yes}$$$ will be recognized as a positive response).

## Examples
```input
11
1337
200
1393938
1434
98765432123456789
11111111111111111
420
1984
10
69
119
```
```output
YES
NO
YES
YES
NO
YES
NO
YES
YES
NO
NO
```

## Note
In the first test case, we can have $$$658 + 679 = 1337$$$.

In the second test case, it can be shown that no numbers of equal length and only consisting of large digits can add to $$$200$$$.

In the third test case, we can have $$$696\,969 + 696\,969 = 1\,393\,938$$$.

In the fourth test case, we can have $$$777 + 657 = 1434$$$.

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
The two versions of the problem are different. You may want to read both versions. You can make hacks only if both versions are solved.

You are given an array $$$a$$$ of length $$$n$$$. Start with $$$c = 0$$$. Then, for each $$$i$$$ from $$$1$$$ to $$$n$$$ (in increasing order) do exactly one of the following:

- Option $$$1$$$: set $$$c$$$ to $$$c + a_i$$$.
- Option $$$2$$$: set $$$c$$$ to $$$|c + a_i|$$$, where $$$|x|$$$ is the absolute value of $$$x$$$.

Let the maximum final value of $$$c$$$ after the procedure described above be equal to $$$k$$$. Find the number of unique procedures that result in $$$c = k$$$. Two procedures are different if at any index $$$i$$$, one procedure chose option $$$1$$$ and another chose option $$$2$$$, even if the value of $$$c$$$ is equal for both procedures after that turn.

Since the answer may be large, output it modulo $$$998\,244\,353$$$.

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

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

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

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

## Output Format
For each test case, output a single integer — the number of unique procedures that result in $$$c = k$$$, modulo $$$998\,244\,353$$$.

## Examples
```input
5
4
2 -5 3 -3
8
1 4 3 4 1 4 3 4
3
-1 -2 -3
4
-1000000000 1000000000 1000000000 1000000000
4
1 9 8 4
```
```output
12
256
1
8
16
```

## Note
In the first test case, it can be shown that our maximal final value of $$$c$$$ is $$$3$$$. There are $$$12$$$ ways to achieve this because in order to get $$$3$$$, we have to take absolute value at indices $$$2$$$ or $$$4$$$, or both, resulting in $$$3$$$ ways. For the other two indices, it doesn't change the value whether we take absolute value or not, so we have $$$2 \cdot 2 = 4$$$ ways for them. In total, we have $$$3 \cdot 4 = 12$$$ ways.

In the second test case, taking the absolute value will never change anything, so we can either take absolute value or not, for every index. This gives us $$$2^8 = 256$$$ possible ways.

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 are given a string $$$s$$$ consisting of lowercase Latin characters. Count the number of nonempty strings $$$t \neq$$$ "$$$\texttt{a}$$$" such that it is possible to partition$$$^{\dagger}$$$ $$$s$$$ into some substrings satisfying the following conditions:

- each substring either equals $$$t$$$ or "$$$\texttt{a}$$$", and
- at least one substring equals $$$t$$$.

$$$^{\dagger}$$$ A partition of a string $$$s$$$ is an ordered sequence of some $$$k$$$ strings $$$t_1, t_2, \ldots, t_k$$$ (called substrings) such that $$$t_1 + t_2 + \ldots + t_k = s$$$, where $$$+$$$ represents the concatenation operation.

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

The only line of each test case contains a string $$$s$$$ consisting of lowercase Latin characters ($$$2 \leq |s| \leq 2 \cdot 10^5$$$).

The sum of $$$|s|$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the number of nonempty strings $$$t \neq$$$ "$$$\texttt{a}$$$" that satisfy all constraints.

## Examples
```input
8
aaaaa
baba
cabacb
aaabaaa
bitset
ab
abbaaaabbb
yearnineteeneightyfour
```
```output
4
4
1
16
1
2
3
1
```

## Note
In the first test case, $$$t$$$ can be "$$$\texttt{aa}$$$", "$$$\texttt{aaa}$$$", "$$$\texttt{aaaa}$$$", or the full string.

In the second test case, $$$t$$$ can be "$$$\texttt{b}$$$", "$$$\texttt{bab}$$$", "$$$\texttt{ba}$$$", or the full string.

In the third test case, the only such $$$t$$$ is the full string.

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
The secret behind Oscar's first magic trick has been revealed! Because he still wants to impress Lura, he comes up with a new idea: he still wants to sort a permutation $$$p_1, p_2, \ldots, p_n$$$ of $$$[1, 2, \ldots, n]$$$.

This time, he chooses an integer $$$k$$$. He wants to sort the permutation in non-decreasing order using the following operation several times:

1. Pick a continuous subarray of length $$$k$$$ and remove it from $$$p$$$.
2. Insert the continuous subarray back into $$$p$$$ at any position (perhaps, in the very front or the very back).

To be as impressive as possible, Oscar would like to choose the maximal value of $$$k$$$ such that he can sort his permutation. Please help him find the maximal $$$k$$$ as well as a sequence of operations that will sort the permutation. You don't need to minimize the number of operations, but you are allowed to use at most $$$5n^2$$$ operations.

We have a proof that, for the maximal $$$k$$$ such that you can sort the permutation in any number of operations, you can also sort it in at most $$$5n^2$$$ operations.

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

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

The second line of each test case contains a permutation $$$p_1, p_2, \ldots, p_n$$$ of $$$[1, 2, \ldots, n]$$$.

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

## Output Format
For each test case, first output the chosen value of $$$k$$$ on a new line ($$$1 \leq k \leq n$$$).

Then, output a single integer $$$m$$$ — the number of operations used ($$$0 \leq m \leq 5n^2$$$).

Then, on each of the next $$$m$$$ lines, output the operations denoted by two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n - k + 1$$$), representing an operation where you remove the subarray starting from index $$$i$$$ and replace it back into $$$p$$$ at index $$$j$$$.

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

## Note
In the first test case, it is enough to move the last four numbers to the front.

In the second test case, it can be shown that we cannot have $$$k = 4$$$ or $$$k = 5$$$. With $$$k = 3$$$, we can move the first three numbers to the end, and then the middle three to the front to sort the permutation.

In the third test case, the permutation is already sorted. We can have $$$k = 6$$$ and use no operations.

Now solve the problem and return the code.