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
Vasya decided to go to the grocery store. He found in his wallet $$$a$$$ coins of $$$1$$$ burle and $$$b$$$ coins of $$$2$$$ burles. He does not yet know the total cost of all goods, so help him find out $$$s$$$ ($$$s > 0$$$): the minimum positive integer amount of money he cannot pay without change or pay at all using only his coins.

For example, if $$$a=1$$$ and $$$b=1$$$ (he has one $$$1$$$-burle coin and one $$$2$$$-burle coin), then:

- he can pay $$$1$$$ burle without change, paying with one $$$1$$$-burle coin,
- he can pay $$$2$$$ burle without change, paying with one $$$2$$$-burle coin,
- he can pay $$$3$$$ burle without change by paying with one $$$1$$$-burle coin and one $$$2$$$-burle coin,
- he cannot pay $$$4$$$ burle without change (moreover, he cannot pay this amount at all).

So for $$$a=1$$$ and $$$b=1$$$ the answer is $$$s=4$$$.

## 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 description of each test case consists of one line containing two integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^8$$$) — the number of $$$1$$$-burle coins and $$$2$$$-burles coins Vasya has respectively.

## Output Format
For each test case, on a separate line print one integer $$$s$$$ ($$$s > 0$$$): the minimum positive integer amount of money that Vasya cannot pay without change or pay at all.

## Examples
```input
5
1 1
4 0
0 2
0 0
2314 2374
```
```output
4
5
1
1
7063
```

## Note
- The first test case of the example is clarified into the main part of the statement.
- In the second test case, Vasya has only $$$1$$$ burle coins, and he can collect either any amount from $$$1$$$ to $$$4$$$, but $$$5$$$ can't.
- In the second test case, Vasya has only $$$2$$$ burle coins, and he cannot pay $$$1$$$ burle without change.
- In the fourth test case you don't have any coins, and he can't even pay $$$1$$$ burle.

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 string $$$a=a_1a_2\dots a_n$$$ is called even if it consists of a concatenation (joining) of strings of length $$$2$$$ consisting of the same characters. In other words, a string $$$a$$$ is even if two conditions are satisfied at the same time:

- its length $$$n$$$ is even;
- for all odd $$$i$$$ ($$$1 \le i \le n - 1$$$), $$$a_i = a_{i+1}$$$ is satisfied.

For example, the following strings are even: "" (empty string), "tt", "aabb", "oooo", and "ttrrrroouuuuuuuukk". The following strings are not even: "aaa", "abab" and "abba".

Given a string $$$s$$$ consisting of lowercase Latin letters. Find the minimum number of characters to remove from the string $$$s$$$ to make it even. The deleted characters do not have to be consecutive.

## Input Format
The first line of input data 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.

Each test case consists of one string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), where $$$|s|$$$ — the length of the string $$$s$$$. The string consists of lowercase Latin letters.

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

## Output Format
For each test case, print a single number — the minimum number of characters that must be removed to make $$$s$$$ even.

## Examples
```input
6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw
```
```output
3
3
2
0
2
7
```

## Note
In the first test case you can remove the characters with indices $$$6$$$, $$$7$$$, and $$$9$$$ to get an even string "aabbddcc".

In the second test case, each character occurs exactly once, so in order to get an even string, you must remove all characters from the string.

In the third test case, you can get an even string "aaaabb" by removing, for example, $$$4$$$-th and $$$6$$$-th characters, or a string "aabbbb" by removing the $$$5$$$-th character and any of the first three.

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
This is the easy version of Problem F. The only difference between the easy version and the hard version is the constraints.

We will call a non-empty string balanced if it contains the same number of plus and minus signs. For example: strings "+--+" and "++-+--" are balanced, and strings "+--", "--" and "" are not balanced.

We will call a string promising if the string can be made balanced by several (possibly zero) uses of the following operation:

- replace two adjacent minus signs with one plus sign.

In particular, every balanced string is promising. However, the converse is not true: not every promising string is balanced.

For example, the string "-+---" is promising, because you can replace two adjacent minuses with plus and get a balanced string "-++-", or get another balanced string "-+-+".

How many non-empty substrings of the given string $$$s$$$ are promising? Each non-empty promising substring must be counted in the answer as many times as it occurs in string $$$s$$$.

Recall that a substring is a sequence of consecutive characters of the string. For example, for string "+-+" its substring are: "+-", "-+", "+", "+-+" (the string is a substring of itself) and some others. But the following strings are not its substring: "--", "++", "-++".

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

Then the descriptions of test cases follow.

Each test case of input data consists of two lines. The first line consists of the number $$$n$$$ ($$$1 \le n \le 3000$$$): the length of $$$s$$$.

The second line of the test case contains the string $$$s$$$ of length $$$n$$$, consisting only of characters "+" and "-".

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

## Output Format
For each test case, print a single number: the number of the promising non-empty substrings of string $$$s$$$. Each non-empty promising substring must be counted in the answer as many times as it occurs in string $$$s$$$.

## Examples
```input
5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---
```
```output
2
4
2
7
4
```

## Note
The following are the promising substrings for the first three test cases in the example:

1. $$$s[1 \dots 2]$$$="+-", $$$s[2 \dots 3]$$$="-+";
2. $$$s[1 \dots 2]$$$="-+", $$$s[2 \dots 3]$$$="+-", $$$s[1 \dots 5]$$$="-+---", $$$s[3 \dots 5]$$$="---";
3. $$$s[1 \dots 3]$$$="---", $$$s[2 \dots 4]$$$="---".

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
It turns out that this is exactly the $$$100$$$-th problem of mine that appears in some programming competition. So it has to be special! And what can be more special than another problem about LIS...

You are given a permutation $$$p_1, p_2, \ldots, p_{2n+1}$$$ of integers from $$$1$$$ to $$$2n+1$$$. You will have to process $$$q$$$ updates, where the $$$i$$$-th update consists in swapping $$$p_{u_i}, p_{v_i}$$$.

After each update, find any cyclic shift of $$$p$$$ with $$$LIS \le n$$$, or determine that there is no such shift. (Refer to the output section for details).

Here $$$LIS(a)$$$ denotes the length of longest strictly increasing subsequence of $$$a$$$.

Hacks are disabled in this problem. Don't ask why.

## Input Format
The first line of the input contains two integers $$$n, q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$).

The second line of the input contains $$$2n+1$$$ integers $$$p_1, p_2, \ldots, p_{2n+1}$$$ ($$$1 \le p_i \le 2n+1$$$, all $$$p_i$$$ are distinct)  — the elements of $$$p$$$.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le 2n+1$$$, $$$u_i \neq v_i$$$)  — indicating that you have to swap elements $$$p_{u_i}, p_{v_i}$$$ in the $$$i$$$-th update.

## Output Format
After each update, output any $$$k$$$ $$$(0 \le k \le 2n)$$$, such that the length of the longest increasing subsequence of $$$(p_{k+1}, p_{k+2}, \ldots, p_{2n+1}, p_1, \ldots, p_k)$$$ doesn't exceed $$$n$$$, or $$$-1$$$, if there is no such $$$k$$$.

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

## Note
After the first update, our permutation becomes $$$(5, 2, 3, 4, 1)$$$. We can show that all its cyclic shifts have $$$LIS \ge 3$$$.

After the second update, our permutation becomes $$$(1, 2, 3, 4, 5)$$$. We can show that all its cyclic shifts have $$$LIS \ge 3$$$.

After the third update, our permutation becomes $$$(1, 2, 3, 5, 4)$$$. Its shift by $$$2$$$ is $$$(3, 5, 4, 1, 2)$$$, and its $$$LIS = 2$$$.

After the fourth update, our permutation becomes $$$(1, 2, 3, 4, 5)$$$. We can show that all its cyclic shifts have $$$LIS \ge 3$$$.

After the fifth update, our permutation becomes $$$(4, 2, 3, 1, 5)$$$. Its shift by $$$4$$$ is $$$(5, 4, 2, 3, 1)$$$, and its $$$LIS = 2$$$.

After the fifth update, our permutation becomes $$$(4, 5, 3, 1, 2)$$$. Its shift by $$$0$$$ is $$$(4, 5, 3, 1, 2)$$$, and its $$$LIS = 2$$$.

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
Monocarp is a little boy who lives in Byteland and he loves programming.

Recently, he found a permutation of length $$$n$$$. He has to come up with a mystic permutation. It has to be a new permutation such that it differs from the old one in each position.

More formally, if the old permutation is $$$p_1,p_2,\ldots,p_n$$$ and the new one is $$$q_1,q_2,\ldots,q_n$$$ it must hold that $$$$$$p_1\neq q_1, p_2\neq q_2, \ldots ,p_n\neq q_n.$$$$$$

Monocarp is afraid of lexicographically large permutations. Can you please help him to find the lexicographically minimal mystic permutation?

## Input Format
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 200$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains a positive integer $$$n$$$ ($$$1\leq n\leq 1000$$$) — the length of the permutation.

The second line of each test case contains $$$n$$$ distinct positive integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$). It's guaranteed that $$$p$$$ is a permutation, i. e. $$$p_i \neq p_j$$$ for all $$$i \neq j$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$1000$$$ over all test cases.

## Output Format
For each test case, output $$$n$$$ positive integers — the lexicographically minimal mystic permutations. If such a permutation does not exist, output $$$-1$$$ instead.

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

## Note
In the first test case possible permutations that are mystic are $$$[2,3,1]$$$ and $$$[3,1,2]$$$. Lexicographically smaller of the two is $$$[2,3,1]$$$.

In the second test case, $$$[1,2,3,4,5]$$$ is the lexicographically minimal permutation and it is also mystic.

In third test case possible mystic permutations are $$$[1,2,4,3]$$$, $$$[1,4,2,3]$$$, $$$[1,4,3,2]$$$, $$$[3,1,4,2]$$$, $$$[3,2,4,1]$$$, $$$[3,4,2,1]$$$, $$$[4,1,2,3]$$$, $$$[4,1,3,2]$$$ and $$$[4,3,2,1]$$$. The smallest one is $$$[1,2,4,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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Lena is a beautiful girl who likes logical puzzles.

As a gift for her birthday, Lena got a matrix puzzle!

The matrix consists of $$$n$$$ rows and $$$m$$$ columns, and each cell is either black or white. The coordinates $$$(i,j)$$$ denote the cell which belongs to the $$$i$$$-th row and $$$j$$$-th column for every $$$1\leq i \leq n$$$ and $$$1\leq j \leq m$$$. To solve the puzzle, Lena has to choose a cell that minimizes the Manhattan distance to the farthest black cell from the chosen cell.

More formally, let there be $$$k \ge 1$$$ black cells in the matrix with coordinates $$$(x_i,y_i)$$$ for every $$$1\leq i \leq k$$$. Lena should choose a cell $$$(a,b)$$$ that minimizes $$$$$$\max_{i=1}^{k}(|a-x_i|+|b-y_i|).$$$$$$

As Lena has no skill, she asked you for help. Will you tell her the optimal cell to choose?

## Input Format
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10\,000$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2\leq n,m \leq 1000$$$)  — the dimensions of the matrix.

The following $$$n$$$ lines contain $$$m$$$ characters each, each character is either 'W' or 'B'. The $$$j$$$-th character in the $$$i$$$-th of these lines is 'W' if the cell $$$(i,j)$$$ is white, and 'B' if the cell $$$(i,j)$$$ is black.

It is guaranteed that at least one black cell exists.

It is guaranteed that the sum of $$$n\cdot m$$$ does not exceed $$$10^6$$$.

## Output Format
For each test case, output the optimal cell $$$(a,b)$$$ to choose. If multiple answers exist, output any.

## Examples
```input
5
3 2
BW
WW
WB
3 3
WWB
WBW
BWW
2 3
BBB
BBB
5 5
BWBWB
WBWBW
BWBWB
WBWBW
BWBWB
9 9
WWWWWWWWW
WWWWWWWWW
BWWWWWWWW
WWWWWWWWW
WWWWBWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWB
```
```output
2 1
2 2
1 2
3 3
6 5
```

## Note
In the first test case the two black cells have coordinates $$$(1,1)$$$ and $$$(3,2)$$$. The four optimal cells are $$$(1,2)$$$, $$$(2,1)$$$, $$$(2,2)$$$ and $$$(3,1)$$$. It can be shown that no other cell minimizes the maximum Manhattan distance to every black cell.

In the second test case it is optimal to choose the black cell $$$(2,2)$$$ with maximum Manhattan distance being $$$2$$$.

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

# Problem
Bit Lightyear, to the ANDfinity and beyond!

After graduating from computer sciences, Vlad has been awarded an array $$$a_1,a_2,\ldots,a_n$$$ of $$$n$$$ non-negative integers. As it is natural, he wanted to construct a graph consisting of $$$n$$$ vertices, numbered $$$1, 2,\ldots, n$$$. He decided to add an edge between $$$i$$$ and $$$j$$$ if and only if $$$a_i \& a_j > 0$$$, where $$$\&$$$ denotes the bitwise AND operation.

Vlad also wants the graph to be connected, which might not be the case initially. In order to satisfy that, he can do the following two types of operations on the array:

1. Choose some element $$$a_i$$$ and increment it by $$$1$$$.
2. Choose some element $$$a_i$$$ and decrement it by $$$1$$$ (possible only if $$$a_i > 0$$$).

It can be proven that there exists a finite sequence of operations such that the graph will be connected. So, can you please help Vlad find the minimum possible number of operations to do that and also provide the way how to do that?

## Input Format
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains an integer $$$n$$$ ($$$2\leq n \leq 2000$$$).

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

## Output Format
For each test case, print a single integer $$$m$$$ in the first line — the minimum number of operations. In the second line print the array after a valid sequence of operations that have been done such that the graph from the task becomes connected.

If there are multiple solutions, output any.

## Examples
```input
4
5
1 2 3 4 5
2
0 2
2
3 12
4
3 0 0 0
```
```output
0
1 2 3 4 5
2
2 2
1
3 11
3
3 1 1 1
```

## Note
In the first test case, the graph is already connected.

In the second test case, we can increment $$$0$$$ twice and end up with the array $$$[2,2]$$$. Since $$$2 \& 2 = 2 > 0$$$, the graph is connected. It can be shown that one operation is not enough.

In the third test case, we can decrement $$$12$$$ once and we end up with an array $$$[3,11]$$$. $$$3 \& 11 = 3 > 0$$$ hence the graph is connected. One operation has to be done since the graph is not connected at the beginning.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ positive integers.

You are allowed to perform this operation any number of times (possibly, zero):

- choose an index $$$i$$$ ($$$2 \le i \le n$$$), and change $$$a_i$$$ to $$$a_i - a_{i-1}$$$.

Is it possible to make $$$a_i=0$$$ for all $$$2\le i\le n$$$?

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

The first line contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

## Output Format
For each test case, print "YES" (without quotes), if it is possible to change $$$a_i$$$ to $$$0$$$ for all $$$2 \le i \le n$$$, and "NO" (without quotes) otherwise.

You can print letters in any case (upper or lower).

## Examples
```input
4
2
5 10
3
1 2 3
4
1 1 1 1
9
9 9 8 2 4 4 3 5 3
```
```output
YES
YES
YES
NO
```

## Note
In the first test case, the initial array is $$$[5,10]$$$. You can perform $$$2$$$ operations to reach the goal:

1. Choose $$$i=2$$$, and the array becomes $$$[5,5]$$$.
2. Choose $$$i=2$$$, and the array becomes $$$[5,0]$$$.

In the second test case, the initial array is $$$[1,2,3]$$$. You can perform $$$4$$$ operations to reach the goal:

1. Choose $$$i=3$$$, and the array becomes $$$[1,2,1]$$$.
2. Choose $$$i=2$$$, and the array becomes $$$[1,1,1]$$$.
3. Choose $$$i=3$$$, and the array becomes $$$[1,1,0]$$$.
4. Choose $$$i=2$$$, and the array becomes $$$[1,0,0]$$$.

In the third test case, you can choose indices in the order $$$4$$$, $$$3$$$, $$$2$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given three integers $$$n$$$, $$$l$$$, and $$$r$$$. You need to construct an array $$$a_1,a_2,\dots,a_n$$$ ($$$l\le a_i\le r$$$) such that $$$\gcd(i,a_i)$$$ are all distinct or report there's no solution.

Here $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

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

The first line contains three integers $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \le n \le 10^5$$$, $$$1\le l\le r\le 10^9$$$).

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

## Output Format
For each test case, if there is no solution, print "NO" (without quotes). You can print letters in any case (upper or lower).

Otherwise, print "YES" (without quotes). In the next line, print $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ — the array you construct.

If there are multiple solutions, you may output any.

## Examples
```input
4
5 1 5
9 1000 2000
10 30 35
1 1000000000 1000000000
```
```output
YES
1 2 3 4 5
YES
1145 1926 1440 1220 1230 1350 1001 1000 1233
NO
YES
1000000000
```

## Note
In the first test case, $$$\gcd(1,a_1),\gcd(2,a_2),\ldots,\gcd(5,a_5)$$$ are equal to $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, respectively.

Now solve the problem and return the code.