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
Inflation has occurred in Berlandia, so the store needs to change the price of goods.

The current price of good $$$n$$$ is given. It is allowed to increase the price of the good by $$$k$$$ times, with $$$1 \le k \le m$$$, k is an integer. Output the roundest possible new price of the good. That is, the one that has the maximum number of zeros at the end.

For example, the number 481000 is more round than the number 1000010 (three zeros at the end of 481000 and only one at the end of 1000010).

If there are several possible variants, output the one in which the new price is maximal.

If it is impossible to get a rounder price, output $$$n \cdot m$$$ (that is, the maximum possible price).

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

Each test case consists of one line.

This line contains two integers: $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$). Where $$$n$$$ is the old price of the good, and the number $$$m$$$ means that you can increase the price $$$n$$$ no more than $$$m$$$ times.

## Output Format
For each test case, output on a separate line the roundest integer of the form $$$n \cdot k$$$ ($$$1 \le k \le m$$$, $$$k$$$ — an integer).

If there are several possible variants, output the one in which the new price (value $$$n \cdot k$$$) is maximal.

If it is impossible to get a more rounded price, output $$$n \cdot m$$$ (that is, the maximum possible price).

## Examples
```input
10
6 11
5 43
13 5
4 16
10050 12345
2 6
4 30
25 10
2 81
1 7
```
```output
60
200
65
60
120600000
10
100
200
100
7
```

## Note
In the first case $$$n = 6$$$, $$$m = 11$$$. We cannot get a number with two zeros or more at the end, because we need to increase the price $$$50$$$ times, but $$$50 > m = 11$$$. The maximum price multiple of $$$10$$$ would be $$$6 \cdot 10 = 60$$$.

In the second case $$$n = 5$$$, $$$m = 43$$$. The maximum price multiple of $$$100$$$ would be $$$5 \cdot 40 = 200$$$.

In the third case, $$$n = 13$$$, $$$m = 5$$$. All possible new prices will not end in $$$0$$$, then you should output $$$n \cdot m = 65$$$.

In the fourth case, you should increase the price $$$15$$$ times.

In the fifth case, increase the price $$$12000$$$ times.

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
A positive number $$$x$$$ of length $$$n$$$ in base $$$p$$$ ($$$2 \le p \le 10^9$$$) is written on the blackboard. The number $$$x$$$ is given as a sequence $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < p$$$) — the digits of $$$x$$$ in order from left to right (most significant to least significant).

Dmitry is very fond of all the digits of this number system, so he wants to see each of them at least once.

In one operation, he can:

- take any number $$$x$$$ written on the board, increase it by $$$1$$$, and write the new value $$$x + 1$$$ on the board.

For example, $$$p=5$$$ and $$$x=234_5$$$.

- Initially, the board contains the digits $$$2$$$, $$$3$$$ and $$$4$$$;
- Dmitry increases the number $$$234_5$$$ by $$$1$$$ and writes down the number $$$240_5$$$. On the board there are digits $$$0, 2, 3, 4$$$;
- Dmitry increases the number $$$240_5$$$ by $$$1$$$ and writes down the number $$$241_5$$$. Now the board contains all the digits from $$$0$$$ to $$$4$$$.

Your task is to determine the minimum number of operations required to make all the digits from $$$0$$$ to $$$p-1$$$ appear on the board at least once.

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

The first line of description of each test case contains two integers $$$n$$$ ($$$1 \le n \le 100$$$) and $$$p$$$ ($$$2 \le p \le 10^9$$$) — the length of the number and the base of the number system.

The second line of the description of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < p$$$) — digits of $$$x$$$ in number system with base $$$p$$$

It is guaranteed that the number $$$x$$$ does not contain leading zeros (that is, $$$a_1>0$$$).

## Output Format
For each test case print a single integer — the minimum number of operations required for Dmitry to get all the digits on the board from $$$0$$$ to $$$p-1$$$.

It can be shown that this always requires a finite number of operations.

## Examples
```input
11
2 3
1 2
4 2
1 1 1 1
6 6
1 2 3 4 5 0
5 2
1 0 1 0 1
3 10
1 2 3
5 1000
4 1 3 2 5
3 5
2 3 4
4 4
3 2 3 0
1 3
2
5 5
1 2 2 2 4
3 4
1 0 1
```
```output
1
1
0
0
7
995
2
1
1
1
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A sequence of $$$n$$$ numbers is called permutation if it contains all numbers from $$$1$$$ to $$$n$$$ exactly once. For example, the sequences [$$$3, 1, 4, 2$$$], [$$$1$$$] and [$$$2,1$$$] are permutations, but [$$$1,2,1$$$], [$$$0,1$$$] and [$$$1,3,4$$$] — are not.

For a permutation $$$p$$$ of even length $$$n$$$ you can make an array $$$b$$$ of length $$$\frac{n}{2}$$$ such that:

- $$$b_i = \max(p_{2i - 1}, p_{2i})$$$ for $$$1 \le i \le \frac{n}{2}$$$

For example, if $$$p$$$ = [$$$2, 4, 3, 1, 5, 6$$$], then:

- $$$b_1 = \max(p_1, p_2) = \max(2, 4) = 4$$$
- $$$b_2 = \max(p_3, p_4) = \max(3,1)=3$$$
- $$$b_3 = \max(p_5, p_6) = \max(5,6) = 6$$$

For a given array $$$b$$$, find the lexicographically minimal permutation $$$p$$$ such that you can make the given array $$$b$$$ from it.

If $$$b$$$ = [$$$4,3,6$$$], then the lexicographically minimal permutation from which it can be made is $$$p$$$ = [$$$1,4,2,3,5,6$$$], since:

- $$$b_1 = \max(p_1, p_2) = \max(1, 4) = 4$$$
- $$$b_2 = \max(p_3, p_4) = \max(2, 3) = 3$$$
- $$$b_3 = \max(p_5, p_6) = \max(5, 6) = 6$$$

A permutation $$$x_1, x_2, \dots, x_n$$$ is lexicographically smaller than a permutation $$$y_1, y_2 \dots, y_n$$$ if and only if there exists such $$$i$$$ ($$$1 \le i \le n$$$) that $$$x_1=y_1, x_2=y_2, \dots, x_{i-1}=y_{i-1}$$$ and $$$x_i<y_i$$$.

## Input Format
The first line of input data 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 of each test case contains one even integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains exactly $$$\frac{n}{2}$$$ integers $$$b_i$$$ ($$$1 \le b_i \le n$$$) — elements of array $$$b$$$.

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

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

- lexicographically minimal permutation $$$p$$$ such that you can make an array $$$b$$$ from it;
- or a number -1 if the permutation you are looking for does not exist.

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

## Note
The first test case is parsed in the problem 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
An array $$$b$$$ is good if the sum of elements of $$$b$$$ is even.

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers. In one operation, you can select an index $$$i$$$ and change $$$a_i := \lfloor \frac{a_i}{2} \rfloor$$$. $$$^\dagger$$$

Find the minimum number of operations (possibly $$$0$$$) needed to make $$$a$$$ good. It can be proven that it is always possible to make $$$a$$$ good.

$$$^\dagger$$$ $$$\lfloor x \rfloor$$$ denotes the floor function — the largest integer less than or equal to $$$x$$$. For example, $$$\lfloor 2.7 \rfloor = 2$$$, $$$\lfloor \pi \rfloor = 3$$$ and $$$\lfloor 5 \rfloor =5$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — representing the array $$$a$$$.

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

## Output Format
For each test case, output the minimum number of operations needed to make $$$a$$$ good.

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

## Note
In the first test case, array $$$a$$$ is already good.

In the second test case, we can perform on index $$$2$$$ twice. After the first operation, array $$$a$$$ becomes $$$[7,2]$$$. After performing on index $$$2$$$ again, $$$a$$$ becomes $$$[7,1]$$$, which is good. It can be proved that it is not possible to make $$$a$$$ good in less number of operations.

In the third test case, $$$a$$$ becomes $$$[0,2,4]$$$ if we perform the operation on index $$$1$$$ once. As $$$[0,2,4]$$$ is good, answer is $$$1$$$.

In the fourth test case, we need to perform the operation on index $$$1$$$ four times. After all operations, $$$a$$$ becomes $$$[0]$$$. It can be proved that it is not possible to make $$$a$$$ good in less number of operations.

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
An array $$$b$$$ of $$$m$$$ positive integers is good if for all pairs $$$i$$$ and $$$j$$$ ($$$1 \leq i,j \leq m$$$), $$$\max(b_i,b_j)$$$ is divisible by $$$\min(b_i,b_j)$$$.

You are given an array $$$a$$$ of $$$n$$$ positive integers. You can perform the following operation:

- Select an index $$$i$$$ ($$$1 \leq i \leq n$$$) and an integer $$$x$$$ ($$$0 \leq x \leq a_i$$$) and add $$$x$$$ to $$$a_i$$$, in other words, $$$a_i := a_i+x$$$.
- After this operation, $$$a_i \leq 10^{18}$$$ should be satisfied.

You have to construct a sequence of at most $$$n$$$ operations that will make $$$a$$$ good. It can be proven that under the constraints of the problem, such a sequence of operations always exists.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — representing the array $$$a$$$.

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

## Output Format
For each test, output a single integer $$$p$$$ ($$$0 \leq p \leq n$$$) — denoting the number of operations in your solution.

In each of the following $$$p$$$ lines, output two space-separated integers — $$$i$$$ and $$$x$$$.

You do not need to minimize the number of operations. It can be proven that a solution always exists.

## Examples
```input
4
4
2 3 5 5
2
4 8
5
3 4 343 5 6
3
31 5 17
```
```output
4
1 2
1 1
2 2
3 0
0
5
1 3
1 4
2 1
5 4
3 7
3
1 29
2 5
3 3
```

## Note
In the first test case, array $$$a$$$ becomes $$$[5,5,5,5]$$$ after the operations. It is easy to see that $$$[5,5,5,5]$$$ is good.

In the second test case, array $$$a$$$ is already good.

In the third test case, after performing the operations, array $$$a$$$ becomes $$$[10,5,350,5,10]$$$, which is good.

In the fourth test case, after performing the operations, array $$$a$$$ becomes $$$[60,10,20]$$$, which is good.

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 binary string$$$^\dagger$$$ $$$b$$$ of odd length $$$m$$$ is good if $$$b_i$$$ is the median$$$^\ddagger$$$ of $$$b[1,i]^\S$$$ for all odd indices $$$i$$$ ($$$1 \leq i \leq m$$$).

For a binary string $$$a$$$ of length $$$k$$$, a binary string $$$b$$$ of length $$$2k-1$$$ is an extension of $$$a$$$ if $$$b_{2i-1}=a_i$$$ for all $$$i$$$ such that $$$1 \leq i \leq k$$$. For example, 1001011 and 1101001 are extensions of the string 1001. String $$$x=$$$1011011 is not an extension of string $$$y=$$$1001 because $$$x_3 \neq y_2$$$. Note that there are $$$2^{k-1}$$$ different extensions of $$$a$$$.

You are given a binary string $$$s$$$ of length $$$n$$$. Find the sum of the number of good extensions over all prefixes of $$$s$$$. In other words, find $$$\sum_{i=1}^{n} f(s[1,i])$$$, where $$$f(x)$$$ gives number of good extensions of string $$$x$$$. Since the answer can be quite large, you only need to find it modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A binary string is a string whose elements are either $$$\mathtt{0}$$$ or $$$\mathtt{1}$$$.

$$$^\ddagger$$$ For a binary string $$$a$$$ of length $$$2m-1$$$, the median of $$$a$$$ is the (unique) element that occurs at least $$$m$$$ times in $$$a$$$.

$$$^\S$$$ $$$a[l,r]$$$ denotes the string of length $$$r-l+1$$$ which is formed by the concatenation of $$$a_l,a_{l+1},\ldots,a_r$$$ in that order.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), where $$$n$$$ is the length of the binary string $$$s$$$.

The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$.

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 the answer modulo $$$998\,244\,353$$$.

## Examples
```input
6
1
1
1
0
2
11
3
010
9
101101111
37
1011011111011010000011011111111011111
```
```output
1
1
3
3
21
365
```

## Note
In the first and second test cases, $$$f(s[1,1])=1$$$.

In the third test case, the answer is $$$f(s[1,1])+f(s[1,2])=1+2=3$$$.

In the fourth test case, the answer is $$$f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3$$$.

$$$f(\mathtt{11})=2$$$ because two good extensions are possible: 101 and 111.

$$$f(\mathtt{01})=1$$$ because only one good extension is possible: 011.

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 an array $$$a$$$ consisting of $$$n$$$ positive integers.

Find any permutation $$$p$$$ of $$$[1,2,\dots,n]$$$ such that:

- $$$p_{i-2} < p_i$$$ for all $$$i$$$, where $$$3 \leq i \leq n$$$, and
- $$$a_{p_{i-1}} \neq a_{p_i}$$$ for all $$$i$$$, where $$$2 \leq i \leq n$$$.

Or report that no such permutation exists.

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

The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 3 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — representing the array $$$a$$$.

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

## Output Format
For each test case, output "NO" if no such permutation exists, otherwise output "YES" in the first line and print the permutation $$$p$$$ in the next line.

In case there are multiple permutations, print any one of them.

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

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

## Note
In the first test case, $$$p=[1,2,3]$$$ is the only permutation of $$$[1,2,3]$$$ that satisfy the given constraints.

In the second test case, $$$[1,3,2,4]$$$, $$$[2,1,4,3]$$$ and some other permutations are also acceptable.

In the third test case, it can be proved that there does not exist any permutation of $$$[1,2,3]$$$ satisfying the given constraints.

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
AquaMoon has a string $$$a$$$ consisting of only $$$0$$$ and $$$1$$$. She wants to add $$$+$$$ and $$$-$$$ between all pairs of consecutive positions to make the absolute value of the resulting expression as small as possible. Can you help her?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\,000$$$)  – the number of test cases. The description of test cases follows.

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

The second line of each test case contains a string $$$a$$$ of length $$$n$$$, consisting of only $$$0$$$ and $$$1$$$.

## Output Format
For each test case, output a string of length $$$n - 1$$$ consisting of $$$-$$$ and $$$+$$$ on a separate line. If there is more than one assignment of signs that produces the smallest possible absolute value, any of them is accepted.

## Examples
```input
3
2
11
5
01101
5
10001
```
```output
-
+-++
+++-
```

## Note
In the first test case, we can get the expression $$$1 - 1 = 0$$$, with absolute value $$$0$$$.

In the second test case, we can get the expression $$$0 + 1 - 1 + 0 + 1 = 1$$$, with absolute value $$$1$$$.

In the third test case, we can get the expression $$$1 + 0 + 0 + 0 - 1 = 0$$$, with absolute value $$$0$$$.

Now solve the problem and return the code.