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
A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex $$$v$$$ (different from root) is the previous to $$$v$$$ vertex on the shortest path from the root to the vertex $$$v$$$. Children of the vertex $$$v$$$ are all vertices for which $$$v$$$ is the parent.

You are given a rooted tree with $$$n$$$ vertices. The vertex $$$1$$$ is the root. Initially, all vertices are healthy.

Each second you do two operations, the spreading operation and, after that, the injection operation:

1. Spreading: for each vertex $$$v$$$, if at least one child of $$$v$$$ is infected, you can spread the disease by infecting at most one other child of $$$v$$$ of your choice.
2. Injection: you can choose any healthy vertex and infect it.

This process repeats each second until the whole tree is infected. You need to find the minimal number of seconds needed to infect the whole tree.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of the vertices in the given tree.

The second line of each test case contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the ancestor of the $$$i$$$-th vertex in the tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case you should output a single integer — the minimal number of seconds needed to infect the whole tree.

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

## Note
The image depicts the tree from the first test case during each second.

A vertex is black if it is not infected. A vertex is blue if it is infected by injection during the previous second. A vertex is green if it is infected by spreading during the previous second. A vertex is red if it is infected earlier than the previous second.

Note that you are able to choose which vertices are infected by spreading and by injections.

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

# Problem
You are given an array $$$a$$$ of $$$n$$$ non-negative integers, numbered from $$$1$$$ to $$$n$$$.

Let's define the cost of the array $$$a$$$ as $$$\displaystyle \min_{i \neq j} a_i | a_j$$$, where $$$|$$$ denotes the bitwise OR operation.

There are $$$q$$$ queries. For each query you are given two integers $$$l$$$ and $$$r$$$ ($$$l < r$$$). For each query you should find the cost of the subarray $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — the elements of $$$a$$$.

The third line of each test case contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$l_j$$$, $$$r_j$$$ ($$$1 \le l_j < r_j \le n$$$) — the description of the $$$j$$$-th query.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$10^5$$$.

## Output Format
For each test case print $$$q$$$ numbers, where the $$$j$$$-th number is the cost of array $$$a_{l_j}, a_{l_j + 1}, \ldots, a_{r_j}$$$.

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

## Note
In the first test case the array $$$a$$$ is

$$$110_2, 001_2, 011_2, 010_2, 001_2$$$.

That's why the answers for the queries are:

- $$$[1; 2]$$$: $$$a_1 | a_2 = 110_2 | 001_2 = 111_2 = 7$$$;
- $$$[2; 3]$$$: $$$a_2 | a_3 = 001_2 | 011_2 = 011_2 = 3$$$;
- $$$[2; 4]$$$: $$$a_2 | a_3 = a_3 | a_4 = a_2 | a_4 = 011_2 = 3$$$;
- $$$[2; 5]$$$: $$$a_2 | a_5 = 001_2 = 1$$$.

In the second test case the array $$$a$$$ is

$$$00_2, 10_2, 01_2, \underbrace{11\ldots 1_2}_{30}$$$ ($$$a_4 = 2^{30} - 1$$$).

That's why the answers for the queries are:

- $$$[1; 2]$$$: $$$a_1 | a_2 = 10_2 = 2$$$;
- $$$[2; 3]$$$: $$$a_2 | a_3 = 11_2 = 3$$$;
- $$$[1; 3]$$$: $$$a_1 | a_3 = 01_2 = 1$$$;
- $$$[3; 4]$$$: $$$a_3 | a_4 = 01_2 | \underbrace{11\ldots 1_2}_{30} = 2^{30} - 1 = 1073741823$$$.

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
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
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 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
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 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 the integer $$$n$$$ — the number of available blocks. You must use all blocks to build a pedestal.

The pedestal consists of $$$3$$$ platforms for $$$2$$$-nd, $$$1$$$-st and $$$3$$$-rd places respectively. The platform for the $$$1$$$-st place must be strictly higher than for the $$$2$$$-nd place, and the platform for the $$$2$$$-nd place must be strictly higher than for the $$$3$$$-rd place. Also, the height of each platform must be greater than zero (that is, each platform must contain at least one block).

Example pedestal of $$$n=11$$$ blocks: second place height equals $$$4$$$ blocks, first place height equals $$$5$$$ blocks, third place height equals $$$2$$$ blocks.

Among all possible pedestals of $$$n$$$ blocks, deduce one such that the platform height for the $$$1$$$-st place minimum as possible. If there are several of them, output any of them.

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

Each test case contains a single integer $$$n$$$ ($$$6 \le n \le 10^5$$$) — the total number of blocks for the pedestal. All $$$n$$$ blocks must be used.

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

## Output Format
For each test case, output $$$3$$$ numbers $$$h_2, h_1, h_3$$$ — the platform heights for $$$2$$$-nd, $$$1$$$-st and $$$3$$$-rd places on a pedestal consisting of $$$n$$$ blocks ($$$h_1+h_2+h_3=n$$$, $$$0 < h_3 < h_2 < h_1$$$).

Among all possible pedestals, output the one for which the value of $$$h_1$$$ minimal. If there are several of them, output any of them.

## Examples
```input
6
11
6
10
100000
7
8
```
```output
4 5 2
2 3 1
4 5 1
33334 33335 33331
2 4 1
3 4 1
```

## Note
In the first test case we can not get the height of the platform for the first place less than $$$5$$$, because if the height of the platform for the first place is not more than $$$4$$$, then we can use at most $$$4 + 3 + 2 = 9$$$ blocks. And we should use $$$11 = 4 + 5 + 2$$$ blocks. Therefore, the answer 4 5 2 fits.

In the second set, the only suitable answer is: 2 3 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
Kristina has two arrays $$$a$$$ and $$$b$$$, each containing $$$n$$$ non-negative integers. She can perform the following operation on array $$$a$$$ any number of times:

- apply a decrement to each non-zero element of the array, that is, replace the value of each element $$$a_i$$$ such that $$$a_i > 0$$$ with the value $$$a_i - 1$$$ ($$$1 \le i \le n$$$). If $$$a_i$$$ was $$$0$$$, its value does not change.

Determine whether Kristina can get an array $$$b$$$ from an array $$$a$$$ in some number of operations (probably zero). In other words, can she make $$$a_i = b_i$$$ after some number of operations for each $$$1 \le i \le n$$$?

For example, let $$$n = 4$$$, $$$a = [3, 5, 4, 1]$$$ and $$$b = [1, 3, 2, 0]$$$. In this case, she can apply the operation twice:

- after the first application of the operation she gets $$$a = [2, 4, 3, 0]$$$;
- after the second use of the operation she gets $$$a = [1, 3, 2, 0]$$$.

Thus, in two operations, she can get an array $$$b$$$ from an array $$$a$$$.

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

The descriptions of the test cases follow.

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

The second line of each test case contains exactly $$$n$$$ non-negative integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

The third line of each test case contains exactly $$$n$$$ non-negative integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \le 10^9$$$).

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

## Output Format
For each test case, output on a separate line:

- YES, if by doing some number of operations it is possible to get an array $$$b$$$ from an array $$$a$$$;
- NO otherwise.

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

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

## Note
The first test case is analyzed in the statement.

In the second test case, it is enough to apply the operation to array $$$a$$$ once.

In the third test case, it is impossible to get array $$$b$$$ from array $$$a$$$.

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 have a stripe of checkered paper of length $$$n$$$. Each cell is either white or black.

What is the minimum number of cells that must be recolored from white to black in order to have a segment of $$$k$$$ consecutive black cells on the stripe?

If the input data is such that a segment of $$$k$$$ consecutive black cells already exists, then print 0.

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

Next, descriptions of $$$t$$$ test cases follow.

The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2\cdot10^5$$$). The second line consists of the letters 'W' (white) and 'B' (black). The line length is $$$n$$$.

It is guaranteed that the sum of values $$$n$$$ does not exceed $$$2\cdot10^5$$$.

## Output Format
For each of $$$t$$$ test cases print an integer — the minimum number of cells that need to be repainted from white to black in order to have a segment of $$$k$$$ consecutive black cells.

## Examples
```input
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W
```
```output
1
2
0
1
```

## Note
In the first test case, $$$s$$$="BBWBW" and $$$k=3$$$. It is enough to recolor $$$s_3$$$ and get $$$s$$$="BBBBW". This string contains a segment of length $$$k=3$$$ consisting of the letters 'B'.

In the second test case of the example $$$s$$$="BBWBW" and $$$k=5$$$. It is enough to recolor $$$s_3$$$ and $$$s_5$$$ and get $$$s$$$="BBBBB". This string contains a segment of length $$$k=5$$$ consisting of the letters 'B'.

In the third test case of the example $$$s$$$="BBWBW" and $$$k=1$$$. The string $$$s$$$ already contains a segment of length $$$k=1$$$ consisting of the letters 'B'.

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

# Problem
Polycarp found the string $$$s$$$ and the permutation $$$p$$$. Their lengths turned out to be the same and equal to $$$n$$$.

A permutation of $$$n$$$ elements — is an array of length $$$n$$$, in which every integer from $$$1$$$ to $$$n$$$ occurs exactly once. For example, $$$[1, 2, 3]$$$ and $$$[4, 3, 5, 1, 2]$$$ are permutations, but $$$[1, 2, 4]$$$, $$$[4, 3, 2, 1, 2]$$$ and $$$[0, 1, 2]$$$ are not.

In one operation he can multiply $$$s$$$ by $$$p$$$, so he replaces $$$s$$$ with string $$$new$$$, in which for any $$$i$$$ from $$$1$$$ to $$$n$$$ it is true that $$$new_i = s_{p_i}$$$. For example, with $$$s=wmbe$$$ and $$$p = [3, 1, 4, 2]$$$, after operation the string will turn to $$$s=s_3 s_1 s_4 s_2=bwem$$$.

Polycarp wondered after how many operations the string would become equal to its initial value for the first time. Since it may take too long, he asks for your help in this matter.

It can be proved that the required number of operations always exists. It can be very large, so use a 64-bit integer type.

## Input Format
The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases in input.

The first line of each case contains single integer $$$n$$$ ($$$1 \le n \le 200$$$) — the length of string and permutation.

The second line of each case contains a string $$$s$$$ of length $$$n$$$, containing lowercase Latin letters.

The third line of each case contains $$$n$$$ integers — permutation $$$p$$$ ($$$1 \le p_i \le n$$$), all $$$p_i$$$ are different.

## Output Format
Output $$$t$$$ lines, each of which contains the answer to the corresponding test case of input. As an answer output single integer — the minimum number of operations, after which the string $$$s$$$ will become the same as it was before operations.

## Examples
```input
3
5
ababa
3 4 5 2 1
5
ababa
2 1 4 5 3
10
codeforces
8 6 1 7 5 2 9 3 10 4
```
```output
1
6
12
```

## Note
In the first sample operation doesn't change the string, so it will become the same as it was after $$$1$$$ operations.

In the second sample the string will change as follows:

- $$$s$$$ = babaa
- $$$s$$$ = abaab
- $$$s$$$ = baaba
- $$$s$$$ = abbaa
- $$$s$$$ = baaab
- $$$s$$$ = ababa

Now solve the problem and return the code.