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

# Problem
You are given a string $$$s$$$. You have to determine whether it is possible to build the string $$$s$$$ out of strings aa, aaa, bb and/or bbb by concatenating them. You can use the strings aa, aaa, bb and/or bbb any number of times and in any order.

For example:

- aaaabbb can be built as aa $$$+$$$ aa $$$+$$$ bbb;
- bbaaaaabbb can be built as bb $$$+$$$ aaa $$$+$$$ aa $$$+$$$ bbb;
- aaaaaa can be built as aa $$$+$$$ aa $$$+$$$ aa;
- abab cannot be built from aa, aaa, bb and/or bbb.

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

Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 50$$$), consisting of characters a and/or b.

## Output Format
For each test case, print YES if it is possible to build the string $$$s$$$. Otherwise, print NO.

You may print each letter in any case (for example, YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

## Examples
```input
8
aaaabbb
bbaaaaabbb
aaaaaa
abab
a
b
aaaab
bbaaa
```
```output
YES
YES
YES
NO
NO
NO
NO
YES
```

## Note
The first four test cases of the example are described in the statement.

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
You are given $$$n$$$ points with integer coordinates on a coordinate axis $$$OX$$$. The coordinate of the $$$i$$$-th point is $$$x_i$$$. All points' coordinates are distinct and given in strictly increasing order.

For each point $$$i$$$, you can do the following operation no more than once: take this point and move it by $$$1$$$ to the left or to the right (i..e., you can change its coordinate $$$x_i$$$ to $$$x_i - 1$$$ or to $$$x_i + 1$$$). In other words, for each point, you choose (separately) its new coordinate. For the $$$i$$$-th point, it can be either $$$x_i - 1$$$, $$$x_i$$$ or $$$x_i + 1$$$.

Your task is to determine if you can move some points as described above in such a way that the new set of points forms a consecutive segment of integers, i. e. for some integer $$$l$$$ the coordinates of points should be equal to $$$l, l + 1, \ldots, l + n - 1$$$.

Note that the resulting points should have distinct coordinates.

You have to answer $$$t$$$ independent test cases.

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

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of points in the set $$$x$$$.

The second line of the test case contains $$$n$$$ integers $$$x_1 < x_2 < \ldots < x_n$$$ ($$$1 \le x_i \le 10^6$$$), where $$$x_i$$$ is the coordinate of the $$$i$$$-th point.

It is guaranteed that the points are given in strictly increasing order (this also means that all coordinates are distinct). It is also guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

## Output Format
For each test case, print the answer — if the set of points from the test case can be moved to form a consecutive segment of integers, print YES, otherwise print NO.

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

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
You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. You are also given $$$x$$$ integers $$$1, 2, \dots, x$$$.

You are asked to insert each of the extra integers into the sequence $$$a$$$. Each integer can be inserted at the beginning of the sequence, at the end of the sequence, or between any elements of the sequence.

The score of the resulting sequence $$$a'$$$ is the sum of absolute differences of adjacent elements in it $$$\left(\sum \limits_{i=1}^{n+x-1} |a'_i - a'_{i+1}|\right)$$$.

What is the smallest possible score of the resulting sequence $$$a'$$$?

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

The first line of each testcase contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n, x \le 2 \cdot 10^5$$$) — the length of the sequence and the number of extra integers.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$).

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

## Output Format
For each testcase, print a single integer — the smallest sum of absolute differences of adjacent elements of the sequence after you insert the extra integers into it.

## Examples
```input
4
1 5
10
3 8
7 2 10
10 2
6 1 5 7 3 3 9 10 10 1
4 10
1 3 1 2
```
```output
9
15
31
13
```

## Note
Here are the sequences with the smallest scores for the example. The underlined elements are the extra integers. Note that there exist other sequences with this smallest score.

- $$$\underline{1}, \underline{2}, \underline{3}, \underline{4}, \underline{5}, 10$$$
- $$$\underline{7}, 7, \underline{6}, \underline{4}, 2, \underline{2}, \underline{1}, \underline{3}, \underline{5}, \underline{8}, 10$$$
- $$$6, \underline{1}, 1, \underline{2}, 5, 7, 3, 3, 9, 10, 10, 1$$$
- $$$1, 3, \underline{1}, 1, 2, \underline{2}, \underline{3}, \underline{4}, \underline{5}, \underline{6}, \underline{7}, \underline{8}, \underline{9}, \underline{10}$$$

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

# Problem
You are given a rooted tree of $$$2^n - 1$$$ vertices. Every vertex of this tree has either $$$0$$$ children, or $$$2$$$ children. All leaves of this tree have the same distance from the root, and for every non-leaf vertex, one of its children is the left one, and the other child is the right one. Formally, you are given a perfect binary tree.

The vertices of the tree are numbered in the following order:

- the root has index $$$1$$$;
- if a vertex has index $$$x$$$, then its left child has index $$$2x$$$, and its right child has index $$$2x+1$$$.

Every vertex of the tree has a letter written on it, either A or B. Let's define the character on the vertex $$$x$$$ as $$$s_x$$$.

Let the preorder string of some vertex $$$x$$$ be defined in the following way:

- if the vertex $$$x$$$ is a leaf, then the preorder string of $$$x$$$ be consisting of only one character $$$s_x$$$;
- otherwise, the preorder string of $$$x$$$ is $$$s_x + f(l_x) + f(r_x)$$$, where $$$+$$$ operator defines concatenation of strings, $$$f(l_x)$$$ is the preorder string of the left child of $$$x$$$, and $$$f(r_x)$$$ is the preorder string of the right child of $$$x$$$.

The preorder string of the tree is the preorder string of its root.

Now, for the problem itself...

You have to calculate the number of different strings that can be obtained as the preorder string of the given tree, if you are allowed to perform the following operation any number of times before constructing the preorder string of the tree:

- choose any non-leaf vertex $$$x$$$, and swap its children (so, the left child becomes the right one, and vice versa).

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 18$$$).

The second line contains a sequence of $$$2^n-1$$$ characters $$$s_1, s_2, \dots, s_{2^n-1}$$$. Each character is either A or B. The characters are not separated by spaces or anything else.

## Output Format
Print one integer — the number of different strings that can be obtained as the preorder string of the given tree, if you can apply any number of operations described in the statement. Since it can be very large, print it modulo $$$998244353$$$.

## Examples
```input
4
BAAAAAAAABBABAB
```
```output
16
```
-----
```input
2
BAA
```
```output
1
```
-----
```input
2
ABA
```
```output
2
```
-----
```input
2
AAB
```
```output
2
```
-----
```input
2
AAA
```
```output
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 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
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 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
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 python3.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You 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 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: 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.