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

# Problem
Spring has come, and the management of the AvtoBus bus fleet has given the order to replace winter tires with summer tires on all buses.

You own a small bus service business and you have just received an order to replace $$$n$$$ tires. You know that the bus fleet owns two types of buses: with two axles (these buses have $$$4$$$ wheels) and with three axles (these buses have $$$6$$$ wheels).

You don't know how many buses of which type the AvtoBus bus fleet owns, so you wonder how many buses the fleet might have. You have to determine the minimum and the maximum number of buses that can be in the fleet if you know that the total number of wheels for all buses is $$$n$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1\,000$$$) — the number of test cases. The following lines contain description of test cases.

The only line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — the total number of wheels for all buses.

## Output Format
For each test case print the answer in a single line using the following format.

Print two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \le y$$$) — the minimum and the maximum possible number of buses that can be in the bus fleet.

If there is no suitable number of buses for the given $$$n$$$, print the number $$$-1$$$ as the answer.

## Examples
```input
4
4
7
24
998244353998244352
```
```output
1 1
-1
4 6
166374058999707392 249561088499561088
```

## Note
In the first test case the total number of wheels is $$$4$$$. It means that there is the only one bus with two axles in the bus fleet.

In the second test case it's easy to show that there is no suitable number of buses with $$$7$$$ wheels in total.

In the third test case the total number of wheels is $$$24$$$. The following options are possible:

- Four buses with three axles.
- Three buses with two axles and two buses with three axles.
- Six buses with two axles.

So the minimum number of buses is $$$4$$$ and the maximum number of buses is $$$6$$$.

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
For an array $$$[b_1, b_2, \ldots, b_m]$$$ define its number of inversions as the number of pairs $$$(i, j)$$$ of integers such that $$$1 \le i < j \le m$$$ and $$$b_i>b_j$$$. Let's call array $$$b$$$ odd if its number of inversions is odd.

For example, array $$$[4, 2, 7]$$$ is odd, as its number of inversions is $$$1$$$, while array $$$[2, 1, 4, 3]$$$ isn't, as its number of inversions is $$$2$$$.

You are given a permutation $$$[p_1, p_2, \ldots, p_n]$$$ of integers from $$$1$$$ to $$$n$$$ (each of them appears exactly once in the permutation). You want to split it into several consecutive subarrays (maybe just one), so that the number of the odd subarrays among them is as large as possible.

What largest number of these subarrays may be odd?

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  — the size of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct)  — the elements of the permutation.

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

## Output Format
For each test case output a single integer  — the largest possible number of odd subarrays that you can get after splitting the permutation into several consecutive subarrays.

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

## Note
In the first and third test cases, no matter how we split our permutation, there won't be any odd subarrays.

In the second test case, we can split our permutation into subarrays $$$[4, 3], [2, 1]$$$, both of which are odd since their numbers of inversions are $$$1$$$.

In the fourth test case, we can split our permutation into a single subarray $$$[2, 1]$$$, which is odd.

In the fifth test case, we can split our permutation into subarrays $$$[4, 5], [6, 1, 2, 3]$$$. The first subarray has $$$0$$$ inversions, and the second has $$$3$$$, so it is odd.

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
Cirno's perfect bitmasks classroom has just started!

Cirno gave her students a positive integer $$$x$$$. As an assignment, her students need to find the minimum positive integer $$$y$$$, which satisfies the following two conditions:

$$$$$$x\ \texttt{and}\ y > 0$$$$$$ $$$$$$x\ \texttt{xor}\ y > 0$$$$$$

Where $$$\texttt{and}$$$ is the bitwise AND operation, and $$$\texttt{xor}$$$ is the bitwise XOR operation.

Among the students was Mystia, who was truly baffled by all these new operators. Please help her!

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

For each test case, the only line of input contains one integer $$$x$$$ ($$$1 \leq x \leq 2^{30}$$$).

## Output Format
For each test case, print a single integer — the minimum number of $$$y$$$.

## Examples
```input
7
1
2
5
9
16
114514
1000000
```
```output
3
3
1
1
17
2
64
```

## Note
Test case 1:

$$$1\; \texttt{and}\; 3=1>0$$$, $$$1\; \texttt{xor}\; 3=2>0$$$.

Test case 2:

$$$2\; \texttt{and}\; 3=2>0$$$, $$$2\; \texttt{xor}\; 3=1>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
Patchouli is making a magical talisman. She initially has $$$n$$$ magical tokens. Their magical power can be represented with positive integers $$$a_1, a_2, \ldots, a_n$$$.

Patchouli may perform the following two operations on the tokens.

- Fusion: Patchouli chooses two tokens, removes them, and creates a new token with magical power equal to the sum of the two chosen tokens.
- Reduction: Patchouli chooses a token with an even value of magical power $$$x$$$, removes it and creates a new token with magical power equal to $$$\frac{x}{2}$$$.

Tokens are more effective when their magical powers are odd values. Please help Patchouli to find the minimum number of operations she needs to make magical powers of all tokens odd values.

## Input Format
Each test contains multiple test cases.

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

For each test case, the first line contains one integer $$$n$$$ ($$$1 \leq n\leq 2\cdot 10^5$$$) — the initial number of tokens.

The second line contains $$$n$$$ intergers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial magical power of the $$$n$$$ tokens.

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, print a single integer — the minimum number of operations Patchouli needs to make all tokens have an odd value of magical power.

It can be shown that under such restrictions the required sequence of operations exists.

## Examples
```input
4
2
1 9
3
1 1 2
3
2 4 8
3
1049600 33792 1280
```
```output
0
1
3
10
```

## Note
Test case 1:

$$$a$$$ consists solely of odd numbers initially.

Test case 2:

Choose the tokens with magical power of $$$1$$$ and $$$2$$$ and perform Fusion. Now $$$a=[1,3]$$$, both are odd numbers.

Test case 3:

Choose the tokens with magical power of $$$2$$$ and $$$8$$$ and perform Fusion. Now $$$a=[4,10]$$$.

Choose the token with magical power of $$$10$$$ and perform Reduction. Now $$$a=[4,5]$$$.

Choose the tokens with magical power of $$$4$$$ and $$$5$$$ and perform Fusion. Now $$$a=[9]$$$, and $$$9$$$ is an odd number.

It can be shown that you can not make all the magical powers odd numbers in less than $$$3$$$ moves, so the answer is $$$3$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Mark is asked to take a group photo of $$$2n$$$ people. The $$$i$$$-th person has height $$$h_i$$$ units.

To do so, he ordered these people into two rows, the front row and the back row, each consisting of $$$n$$$ people. However, to ensure that everyone is seen properly, the $$$j$$$-th person of the back row must be at least $$$x$$$ units taller than the $$$j$$$-th person of the front row for each $$$j$$$ between $$$1$$$ and $$$n$$$, inclusive.

Help Mark determine if this is possible.

## Input Format
The first line contains one integer $$$t$$$ ($$$1\leq t\leq 100$$$) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains two positive integers $$$n$$$ and $$$x$$$ ($$$1\leq n\leq 100$$$, $$$1\leq x\leq 10^3$$$) — the number of people in each row and the minimum difference Mark wants.

The second line of each test case contains $$$2n$$$ positive integers $$$h_1,h_2,\ldots,h_{2n}$$$ ($$$1\leq h_i\leq 10^3$$$) — the height of each person in units.

Note that the sum of $$$n$$$ over all test cases is not bounded.

## Output Format
For each test case, print a single line containing "YES" if Mark could arrange people satisfying his condition and "NO" otherwise.

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

## Examples
```input
3
3 6
1 3 9 10 12 16
3 1
2 5 2 2 2 5
1 2
8 6
```
```output
YES
NO
YES
```

## Note
In the first test case, one possible order is to have the third, fifth, and sixth person on the back row and the second, first, and fourth on the front row. The heights of the people will look like this.

Back$$$9$$$$$$12$$$$$$16$$$Front$$$3$$$$$$1$$$$$$10$$$

It works because

- $$$h_3-h_2 = 9-3 \geq 6$$$,
- $$$h_5-h_1 = 12-1\geq 6$$$, and
- $$$h_6-h_4 = 16-10\geq 6$$$.

In the second test case, it can be shown there is no way to order people in a way that satisfies the condition.

In the third test case, the only way to arrange people to satisfy the condition is to have the first person on the back row and the second person on the front row.

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

# Problem
Mark is cleaning a row of $$$n$$$ rooms. The $$$i$$$-th room has a nonnegative dust level $$$a_i$$$. He has a magical cleaning machine that can do the following three-step operation.

- Select two indices $$$i<j$$$ such that the dust levels $$$a_i$$$, $$$a_{i+1}$$$, $$$\dots$$$, $$$a_{j-1}$$$ are all strictly greater than $$$0$$$.
- Set $$$a_i$$$ to $$$a_i-1$$$.
- Set $$$a_j$$$ to $$$a_j+1$$$.

## 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 number of rooms.

The second line of each test case contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0\leq a_i\leq 10^9$$$) — the dust level of each room.

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, print a line containing a single integer — the minimum number of operations. It can be proven that there is a sequence of operations that meets the goal.

## Examples
```input
4
3
2 0 0
5
0 2 0 2 0
6
2 0 3 0 4 6
4
0 0 0 10
```
```output
3
5
11
0
```

## Note
In the first case, one possible sequence of operations is as follows.

- Choose $$$i=1$$$ and $$$j=2$$$, yielding the array $$$[1,1,0]$$$.
- Choose $$$i=1$$$ and $$$j=3$$$, yielding the array $$$[0,1,1]$$$.
- Choose $$$i=2$$$ and $$$j=3$$$, yielding the array $$$[0,0,2]$$$.

In the second case, one possible sequence of operations is as follows.

- Choose $$$i=4$$$ and $$$j=5$$$, yielding the array $$$[0,2,0,1,1]$$$.
- Choose $$$i=2$$$ and $$$j=3$$$, yielding the array $$$[0,1,1,1,1]$$$.
- Choose $$$i=2$$$ and $$$j=5$$$, yielding the array $$$[0,0,1,1,2]$$$.
- Choose $$$i=3$$$ and $$$j=5$$$, yielding the array $$$[0,0,0,1,3]$$$.
- Choose $$$i=4$$$ and $$$j=5$$$, yielding the array $$$[0,0,0,0,4]$$$.

In the last case, the array already satisfies the condition.

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
Polycarpus has n friends in Tarasov city. Polycarpus knows phone numbers of all his friends: they are strings s1, s2, ..., sn. All these strings consist only of digits and have the same length.

Once Polycarpus needed to figure out Tarasov city phone code. He assumed that the phone code of the city is the longest common prefix of all phone numbers of his friends. In other words, it is the longest string c which is a prefix (the beginning) of each si for all i (1 ≤ i ≤ n). Help Polycarpus determine the length of the city phone code.

## Input Format
The first line of the input contains an integer n (2 ≤ n ≤ 3·104) — the number of Polycarpus's friends. The following n lines contain strings s1, s2, ..., sn — the phone numbers of Polycarpus's friends. It is guaranteed that all strings consist only of digits and have the same length from 1 to 20, inclusive. It is also guaranteed that all strings are different.

## Output Format
Print the number of digits in the city phone code.

## Examples
```input
4
00209
00219
00999
00909
```
```output
2
```
-----
```input
2
1
2
```
```output
0
```
-----
```input
3
77012345678999999999
77012345678901234567
77012345678998765432
```
```output
12
```

## Note
A prefix of string t is a string that is obtained by deleting zero or more digits from the end of string t. For example, string "00209" has 6 prefixes: "" (an empty prefix), "0", "00", "002", "0020", "00209".

In the first sample the city phone code is string "00".

In the second sample the city phone code is an empty string.

In the third sample the city phone code is string "770123456789".

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
Polycarpus has recently got interested in sequences of pseudorandom numbers. He learned that many programming languages generate such sequences in a similar way: $$r_{i} = (a \cdot r_{i-1} + b) \mod m$$ (for i ≥ 1). Here a, b, m are constants, fixed for the given realization of the pseudorandom numbers generator, r0 is the so-called randseed (this value can be set from the program using functions like RandSeed(r) or srand(n)), and $$\bmod$$ denotes the operation of taking the remainder of division.

For example, if a = 2, b = 6, m = 12, r0 = 11, the generated sequence will be: 4, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, ....

Polycarpus realized that any such sequence will sooner or later form a cycle, but the cycle may occur not in the beginning, so there exist a preperiod and a period. The example above shows a preperiod equal to 1 and a period equal to 2.

Your task is to find the period of a sequence defined by the given values of a, b, m and r0. Formally, you have to find such minimum positive integer t, for which exists such positive integer k, that for any i ≥ k: ri = ri + t.

## Input Format
The single line of the input contains four integers a, b, m and r0 (1 ≤ m ≤ 105, 0 ≤ a, b ≤ 1000, 0 ≤ r0 < m), separated by single spaces.

## Output Format
Print a single integer — the period of the sequence.

## Examples
```input
2 6 12 11
```
```output
2
```
-----
```input
2 3 5 1
```
```output
4
```
-----
```input
3 6 81 9
```
```output
1
```

## Note
The first sample is described above.

In the second sample the sequence is (starting from the first element): 0, 3, 4, 1, 0, 3, 4, 1, 0, ...

In the third sample the sequence is (starting from the first element): 33, 24, 78, 78, 78, 78, ...

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
Timur likes his name. As a spelling of his name, he allows any permutation of the letters of the name. For example, the following strings are valid spellings of his name: Timur, miurT, Trumi, mriTu. Note that the correct spelling must have uppercased T and lowercased other letters.

Today he wrote string $$$s$$$ of length $$$n$$$ consisting only of uppercase or lowercase Latin letters. He asks you to check if $$$s$$$ is the correct spelling of his name.

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

The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 10)$$$ — the length of string $$$s$$$.

The second line of each test case contains a string $$$s$$$ consisting of only uppercase or lowercase Latin characters.

## Output Format
For each test case, output "YES" (without quotes) if $$$s$$$ satisfies the condition, and "NO" (without quotes) otherwise.

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

## Examples
```input
10
5
Timur
5
miurT
5
Trumi
5
mriTu
5
timur
4
Timr
6
Timuur
10
codeforces
10
TimurTimur
5
TIMUR
```
```output
YES
YES
YES
YES
NO
NO
NO
NO
NO
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
Vasya has a grid with $$$2$$$ rows and $$$n$$$ columns. He colours each cell red, green, or blue.

Vasya is colourblind and can't distinguish green from blue. Determine if Vasya will consider the two rows of the grid to be coloured the same.

## 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. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of columns of the grid.

The following two lines each contain a string consisting of $$$n$$$ characters, each of which is either R, G, or B, representing a red, green, or blue cell, respectively — the description of the grid.

## Output Format
For each test case, output "YES" if Vasya considers the grid's two rows to be identical, and "NO" otherwise.

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

## Examples
```input
6
2
RG
RB
4
GRBG
GBGB
5
GGGGG
BBBBB
7
BBBBBBB
RRRRRRR
8
RGBRRGBR
RGGRRBGR
1
G
G
```
```output
YES
NO
YES
NO
YES
YES
```

## Note
In the first test case, Vasya sees the second cell of each row as the same because the second cell of the first row is green and the second cell of the second row is blue, so he can't distinguish these two cells. The rest of the rows are equal in colour. Therefore, Vasya will say that the two rows are coloured the same, even though they aren't.

In the second test case, Vasya can see that the two rows are different.

In the third test case, every cell is green or blue, so Vasya will think they are the same.

Now solve the problem and return the code.