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
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 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
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 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
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 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
Tokitsukaze has a sequence $$$a$$$ of length $$$n$$$. For each operation, she selects two numbers $$$a_i$$$ and $$$a_j$$$ ($$$i \ne j$$$; $$$1 \leq i,j \leq n$$$).

- If $$$a_i = a_j$$$, change one of them to $$$0$$$.
- Otherwise change both of them to $$$\min(a_i, a_j)$$$.

Tokitsukaze wants to know the minimum number of operations to change all numbers in the sequence to $$$0$$$. It can be proved that the answer always exists.

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

For each test case, the first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the length of the sequence $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 100$$$) — the sequence $$$a$$$.

## Output Format
For each test case, print a single integer — the minimum number of operations to change all numbers in the sequence to $$$0$$$.

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

## Note
In the first test case, one of the possible ways to change all numbers in the sequence to $$$0$$$:

In the $$$1$$$-st operation, $$$a_1 < a_2$$$, after the operation, $$$a_2 = a_1 = 1$$$. Now the sequence $$$a$$$ is $$$[1,1,3]$$$.

In the $$$2$$$-nd operation, $$$a_1 = a_2 = 1$$$, after the operation, $$$a_1 = 0$$$. Now the sequence $$$a$$$ is $$$[0,1,3]$$$.

In the $$$3$$$-rd operation, $$$a_1 < a_2$$$, after the operation, $$$a_2 = 0$$$. Now the sequence $$$a$$$ is $$$[0,0,3]$$$.

In the $$$4$$$-th operation, $$$a_2 < a_3$$$, after the operation, $$$a_3 = 0$$$. Now the sequence $$$a$$$ is $$$[0,0,0]$$$.

So the minimum number of operations is $$$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 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
This is the easy version of the problem. The only difference between the two versions is that the harder version asks additionally for a minimum number of subsegments.

Tokitsukaze has a binary string $$$s$$$ of length $$$n$$$, consisting only of zeros and ones, $$$n$$$ is even.

Now Tokitsukaze divides $$$s$$$ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $$$s$$$ is considered good if the lengths of all subsegments are even.

For example, if $$$s$$$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $$$2$$$, $$$2$$$, $$$4$$$ respectively, which are all even numbers, so "11001111" is good. Another example, if $$$s$$$ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $$$3$$$, $$$2$$$, $$$2$$$, $$$3$$$. Obviously, "1110011000" is not good.

Tokitsukaze wants to make $$$s$$$ good by changing the values of some positions in $$$s$$$. Specifically, she can perform the operation any number of times: change the value of $$$s_i$$$ to '0' or '1'($$$1 \leq i \leq n$$$). Can you tell her the minimum number of operations to make $$$s$$$ good?

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

For each test case, the first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of $$$s$$$, it is guaranteed that $$$n$$$ is even.

The second line contains a binary string $$$s$$$ of length $$$n$$$, consisting only of zeros and ones.

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 line with one integer — the minimum number of operations to make $$$s$$$ good.

## Examples
```input
5
10
1110011000
8
11001111
2
00
2
11
6
100110
```
```output
3
0
0
0
3
```

## Note
In the first test case, one of the ways to make $$$s$$$ good is the following.

Change $$$s_3$$$, $$$s_6$$$ and $$$s_7$$$ to '0', after that $$$s$$$ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $$$2$$$ and $$$8$$$ respectively. There are other ways to operate $$$3$$$ times to make $$$s$$$ good, such as "1111110000", "1100001100", "1111001100".

In the second, third and fourth test cases, $$$s$$$ is good initially, so no operation is required.

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
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 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
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 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: 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 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 a sequence $$$a_1, a_2, \ldots, a_n$$$, find the minimum number of elements to remove from the sequence such that after the removal, the sum of every $$$2$$$ consecutive elements is even.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2,\dots,a_n$$$ ($$$1\leq a_i\leq10^9$$$) — elements of the sequence.

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

## Output Format
For each test case, print a single integer — the minimum number of elements to remove from the sequence such that the sum of every $$$2$$$ consecutive elements is even.

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

## Note
In the first test case, after removing $$$3$$$, the sequence becomes $$$[2,4,6,8]$$$. The pairs of consecutive elements are $$$\{[2, 4], [4, 6], [6, 8]\}$$$. Each consecutive pair has an even sum now. Hence, we only need to remove $$$1$$$ element to satisfy the condition asked.

In the second test case, each consecutive pair already has an even sum so we need not remove any element.

Now solve the problem and return the code.