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
Demodogs from the Upside-down have attacked Hawkins again. El wants to reach Mike and also kill as many Demodogs in the way as possible.

Hawkins can be represented as an $$$n \times n$$$ grid. The number of Demodogs in a cell at the $$$i$$$-th row and the $$$j$$$-th column is $$$i \cdot j$$$. El is at position $$$(1, 1)$$$ of the grid, and she has to reach $$$(n, n)$$$ where she can find Mike.

The only directions she can move are the right (from $$$(i, j)$$$ to $$$(i, j + 1)$$$) and the down (from $$$(i, j)$$$ to $$$(i + 1, j)$$$). She can't go out of the grid, as there are doors to the Upside-down at the boundaries.

Calculate the maximum possible number of Demodogs $$$\mathrm{ans}$$$ she can kill on the way, considering that she kills all Demodogs in cells she visits (including starting and finishing cells).

Print $$$2022 \cdot \mathrm{ans}$$$ modulo $$$10^9 + 7$$$. Modulo $$$10^9 + 7$$$ because the result can be too large and multiplied by $$$2022$$$ because we are never gonna see it again!

(Note, you firstly multiply by $$$2022$$$ and only after that take the remainder.)

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

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^9$$$) — the size of the grid.

## Output Format
For each test case, print a single integer — the maximum number of Demodogs that can be killed multiplied by $$$2022$$$, modulo $$$10^9 + 7$$$.

## Examples
```input
4
2
3
50
1000000000
```
```output
14154
44484
171010650
999589541
```

## Note
In the first test case, for any path chosen by her the number of Demodogs to be killed would be $$$7$$$, so the answer would be $$$2022 \cdot 7 = 14154$$$.

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
Suppose you have an integer array $$$a_1, a_2, \dots, a_n$$$.

Let $$$\operatorname{lsl}(i)$$$ be the number of indices $$$j$$$ ($$$1 \le j < i$$$) such that $$$a_j < a_i$$$.

Analogically, let $$$\operatorname{grr}(i)$$$ be the number of indices $$$j$$$ ($$$i < j \le n$$$) such that $$$a_j > a_i$$$.

Let's name position $$$i$$$ good in the array $$$a$$$ if $$$\operatorname{lsl}(i) < \operatorname{grr}(i)$$$.

Finally, let's define a function $$$f$$$ on array $$$a$$$ $$$f(a)$$$ as the sum of all $$$a_i$$$ such that $$$i$$$ is good in $$$a$$$.

Given two integers $$$n$$$ and $$$k$$$, find the sum of $$$f(a)$$$ over all arrays $$$a$$$ of size $$$n$$$ such that $$$1 \leq a_i \leq k$$$ for all $$$1 \leq i \leq n$$$ modulo $$$998\,244\,353$$$.

## Input Format
The first and only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 50$$$; $$$2 \leq k < 998\,244\,353$$$).

## Output Format
Output a single integer — the sum of $$$f$$$ over all arrays $$$a$$$ of size $$$n$$$ modulo $$$998\,244\,353$$$.

## Examples
```input
3 3
```
```output
28
```
-----
```input
5 6
```
```output
34475
```
-----
```input
12 30
```
```output
920711694
```

## Note
In the first test case:

$$$f([1,1,1]) = 0$$$$$$f([2,2,3]) = 2 + 2 = 4$$$$$$f([1,1,2]) = 1 + 1 = 2$$$$$$f([2,3,1]) = 2$$$$$$f([1,1,3]) = 1 + 1 = 2$$$$$$f([2,3,2]) = 2$$$$$$f([1,2,1]) = 1$$$$$$f([2,3,3]) = 2$$$$$$f([1,2,2]) = 1$$$$$$f([3,1,1]) = 0$$$$$$f([1,2,3]) = 1$$$$$$f([3,1,2]) = 1$$$$$$f([1,3,1]) = 1$$$$$$f([3,1,3]) = 1$$$$$$f([1,3,2]) = 1$$$$$$f([3,2,1]) = 0$$$$$$f([1,3,3]) = 1$$$$$$f([3,2,2]) = 0$$$$$$f([2,1,1]) = 0$$$$$$f([3,2,3]) = 2$$$$$$f([2,1,2]) = 1$$$$$$f([3,3,1]) = 0$$$$$$f([2,1,3]) = 2 + 1 = 3$$$$$$f([3,3,2]) = 0$$$$$$f([2,2,1]) = 0$$$$$$f([3,3,3]) = 0$$$$$$f([2,2,2]) = 0$$$

Adding up all of these values, we get $$$28$$$ as the answer.

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
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 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
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 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 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 c++17.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You 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 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
The famous store "Second Food" sells groceries only two days a month. And the prices in each of days differ. You wanted to buy $$$n$$$ kilos of potatoes for a month. You know that on the first day of the month $$$1$$$ kilo of potatoes costs $$$a$$$ coins, and on the second day $$$b$$$ coins. In "Second Food" you can buy any integer kilograms of potatoes.

Fortunately, "Second Food" has announced a promotion for potatoes, which is valid only on the first day of the month — for each $$$m$$$ kilos of potatoes you buy, you get $$$1$$$ kilo as a gift! In other words, you can get $$$m + 1$$$ kilograms by paying for $$$m$$$ kilograms.

Find the minimum number of coins that you have to spend to buy at least $$$n$$$ kilos of potatoes.

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

The first line of each test case contains two integers $$$a$$$ and $$$b$$$ $$$(1 \leq a, b \leq 10^9)$$$ — the prices of $$$1$$$ kilo of potatoes on the first and second days, respectively.

The second line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^9)$$$ — the required amount of potatoes to buy and the amount of potatoes to use the promotion.

## Output Format
For each test case print one integer — the minimum number of coins that you have to pay to buy at least $$$n$$$ kilos of potatoes.

## Examples
```input
5
5 4
3 1
5 4
3 2
3 4
3 5
20 15
10 2
1000000000 900000000
1000000000 8
```
```output
9
10
9
135
888888888900000000
```

## Note
In the first test case, on the first day you buy $$$1$$$ kilo and get $$$1$$$ more for a promotion. On the second day, you can buy $$$1$$$ kilo of potatoes. Thus, you will spend $$$5+4=9$$$ coins in total.

In the second test case, on the first day you buy $$$2$$$ kilo and get another $$$1$$$ more for a promotion. This way you will spend $$$2 \cdot 5 = 10$$$ coins.

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
For his birthday recently Fedya was given an array $$$a$$$ of $$$n$$$ integers arranged in a circle, For each pair of neighboring numbers ($$$a_1$$$ and $$$a_2$$$, $$$a_2$$$ and $$$a_3$$$, $$$\ldots$$$, $$$a_{n - 1}$$$ and $$$a_n$$$, $$$a_n$$$ and $$$a_1$$$) the absolute difference between them is equal to $$$1$$$.

Let's call a local maximum an element, which is greater than both of its neighboring elements. Also call a local minimum an element, which is less than both of its neighboring elements. Note, that elements $$$a_1$$$ and $$$a_n$$$ are neighboring elements.

Unfortunately, Fedya lost an array, but he remembered in it the sum of local maximums $$$x$$$ and the sum of local minimums $$$y$$$.

Given $$$x$$$ and $$$y$$$, help Fedya find any matching array of minimum length.

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

Each line of each test case contain two integers $$$x$$$ and $$$y$$$ ($$$-10^{9} \le y < x \le 10^{9}$$$) — the sum of local maximums and the sum of local minimums, respectively.

## Output Format
For each test case, in the first line print one integer $$$n$$$ — the minimum length of matching arrays.

In the second line print $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \leqslant a_i \leqslant 10^{9}$$$) — the array elements such that the the absolute difference between each pair of neighboring is equal to $$$1$$$.

If there are multiple solutions, print any of them.

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

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

## Note
In the first test case, the local maximums are the numbers at $$$3, 7$$$ and $$$10$$$ positions, and the local minimums are the numbers at $$$1, 6$$$ and $$$8$$$ positions. $$$x = a_3 + a_7 + a_{10} = 2 + 0 + 1 = 3$$$, $$$y = a_1 + a_6 + a_8 = 0 + (-1) + (-1) = -2$$$.

In the second test case, the local maximums are the numbers at $$$2$$$ and $$$10$$$ positions, and the local minimums are the numbers at $$$1$$$ and $$$3$$$ positions. $$$x = a_2 + a_{10} = -1 + 5 = 4$$$, $$$y = a_1 + a_3 = -2 + (-2) = -4$$$.

In the third test case, the local maximums are the numbers at $$$1$$$ and $$$5$$$ positions, and the local minimums are the numbers at $$$3$$$ and $$$6$$$ positions.

Now solve the problem and return the code.