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

# Problem
// We decided to drop the legend about the power sockets but feel free to come up with your own :^)

Define a chain:

- a chain of length $$$1$$$ is a single vertex;
- a chain of length $$$x$$$ is a chain of length $$$x-1$$$ with a new vertex connected to the end of it with a single edge.

You are given $$$n$$$ chains of lengths $$$l_1, l_2, \dots, l_n$$$. You plan to build a tree using some of them.

- Each vertex of the tree is either white or black.
- The tree initially only has a white root vertex.
- All chains initially consist only of white vertices.
- You can take one of the chains and connect any of its vertices to any white vertex of the tree with an edge. The chain becomes part of the tree. Both endpoints of this edge become black.
- Each chain can be used no more than once.
- Some chains can be left unused.

The distance between two vertices of the tree is the number of edges on the shortest path between them.

If there is at least $$$k$$$ white vertices in the resulting tree, then the value of the tree is the distance between the root and the $$$k$$$-th closest white vertex.

What's the minimum value of the tree you can obtain? If there is no way to build a tree with at least $$$k$$$ white vertices, then print -1.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) — the number of chains and the minimum number of white vertices a tree should have to have a value.

The second line contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$3 \le l_i \le 2 \cdot 10^5$$$) — the lengths of the chains.

## Output Format
Print a single integer. If there is no way to build a tree with at least $$$k$$$ white vertices, then print -1. Otherwise, print the minimum value the tree can have.

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

## Note
You are allowed to not use all the chains, so it's optimal to only use chain of length $$$4$$$ in the second example.

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
You are given an array $$$a$$$ of length $$$n$$$, and an integer $$$x$$$. You can perform the following operation as many times as you would like (possibly zero): replace two adjacent elements of the array by their sum. For example, if the initial array was $$$[3, 6, 9]$$$, in a single operation one can replace the last two elements by their sum, yielding an array $$$[3, 15]$$$, or replace the first two elements to get an array $$$[9, 9]$$$. Note that the size of the array decreases after each operation.

The beauty of an array $$$b=[b_1, \ldots, b_k]$$$ is defined as $$$\sum_{i=1}^k \left\lceil \frac{b_i}{x} \right\rceil$$$, which means that we divide each element by $$$x$$$, round it up to the nearest integer, and sum up the resulting values. For example, if $$$x = 3$$$, and the array is $$$[4, 11, 6]$$$, the beauty of the array is equal to $$$\left\lceil \frac{4}{3} \right\rceil + \left\lceil \frac{11}{3} \right\rceil + \left\lceil \frac{6}{3} \right\rceil = 2 + 4 + 2 = 8$$$.

Please determine the minimum and the maximum beauty you can get by performing some operations on the original array.

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

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq x \leq 10^9$$$).

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), the elements of the array $$$a$$$.

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

## Output Format
For each test case output two integers — the minimal and the maximal possible beauty.

## Examples
```input
2
3 3
3 6 9
3 3
6 4 11
```
```output
6 6
7 8
```

## Note
In the first test case the beauty of the array does not change if we perform any operations.

In the second example we can leave the array unchanged to attain the maximum beauty, and to get the minimum beauty one can replace two elements $$$4$$$ and $$$11$$$ with their sum, yielding an array $$$[6, 15]$$$, which has its beauty equal to $$$7$$$.

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
You have given an array $$$a$$$ of length $$$n$$$ and an integer $$$x$$$ to a brand new robot. What the robot does is the following: it iterates over the elements of the array, let the current element be $$$q$$$. If $$$q$$$ is divisible by $$$x$$$, the robot adds $$$x$$$ copies of the integer $$$\frac{q}{x}$$$ to the end of the array, and moves on to the next element. Note that the newly added elements could be processed by the robot later. Otherwise, if $$$q$$$ is not divisible by $$$x$$$, the robot shuts down.

Please determine the sum of all values of the array at the end of the process.

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

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$2 \leq x \leq 10^9$$$) — the length of the array and the value which is used by the robot.

The next line contains integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial values in the array.

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

## Output Format
For each test case output one integer — the sum of all elements at the end of the process.

## Examples
```input
2
1 2
12
4 2
4 6 8 2
```
```output
36
44
```

## Note
In the first test case the array initially consists of a single element $$$[12]$$$, and $$$x=2$$$. After the robot processes the first element, the array becomes $$$[12, 6, 6]$$$. Then the robot processes the second element, and the array becomes $$$[12, 6, 6, 3, 3]$$$. After the robot processes the next element, the array becomes $$$[12, 6, 6, 3, 3, 3, 3]$$$, and then the robot shuts down, since it encounters an element that is not divisible by $$$x = 2$$$. The sum of the elements in the resulting array is equal to $$$36$$$.

In the second test case the array initially contains integers $$$[4, 6, 8, 2]$$$, and $$$x=2$$$. The resulting array in this case looks like $$$ [4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1, 1, 1, 1, 1]$$$.

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Homer has two friends Alice and Bob. Both of them are string fans.

One day, Alice and Bob decide to play a game on a string $$$s = s_1 s_2 \dots s_n$$$ of length $$$n$$$ consisting of lowercase English letters. They move in turns alternatively and Alice makes the first move.

In a move, a player must choose an index $$$i$$$ ($$$1 \leq i \leq n$$$) that has not been chosen before, and change $$$s_i$$$ to any other lowercase English letter $$$c$$$ that $$$c \neq s_i$$$.

When all indices have been chosen, the game ends.

The goal of Alice is to make the final string lexicographically as small as possible, while the goal of Bob is to make the final string lexicographically as large as possible. Both of them are game experts, so they always play games optimally. Homer is not a game expert, so he wonders what the final string will be.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

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

The only line of each test case contains a single string $$$s$$$ ($$$1 \leq |s| \leq 50$$$) consisting of lowercase English letters.

## Output Format
For each test case, print the final string in a single line.

## Examples
```input
3
a
bbbb
az
```
```output
b
azaz
by
```

## Note
In the first test case: Alice makes the first move and must change the only letter to a different one, so she changes it to 'b'.

In the second test case: Alice changes the first letter to 'a', then Bob changes the second letter to 'z', Alice changes the third letter to 'a' and then Bob changes the fourth letter to 'z'.

In the third test case: Alice changes the first letter to 'b', and then Bob changes the second letter to 'y'.

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
Kawashiro Nitori is a girl who loves competitive programming.

One day she found a string and an integer. As an advanced problem setter, she quickly thought of a problem.

Given a string $$$s$$$ and a parameter $$$k$$$, you need to check if there exist $$$k+1$$$ non-empty strings $$$a_1,a_2...,a_{k+1}$$$, such that $$$$$$s=a_1+a_2+\ldots +a_k+a_{k+1}+R(a_k)+R(a_{k-1})+\ldots+R(a_{1}).$$$$$$

Here $$$+$$$ represents concatenation. We define $$$R(x)$$$ as a reversed string $$$x$$$. For example $$$R(abcd) = dcba$$$. Note that in the formula above the part $$$R(a_{k+1})$$$ is intentionally skipped.

## 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 of each test case description contains two integers $$$n$$$, $$$k$$$ ($$$1\le n\le 100$$$, $$$0\le k\le \lfloor \frac{n}{2} \rfloor$$$)  — the length of the string $$$s$$$ and the parameter $$$k$$$.

The second line of each test case description contains a single string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

## Output Format
For each test case, print "YES" (without quotes), if it is possible to find $$$a_1,a_2,\ldots,a_{k+1}$$$, and "NO" (without quotes) otherwise.

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

## Examples
```input
7
5 1
qwqwq
2 1
ab
3 1
ioi
4 2
icpc
22 0
dokidokiliteratureclub
19 8
imteamshanghaialice
6 3
aaaaaa
```
```output
YES
NO
YES
NO
YES
NO
NO
```

## Note
In the first test case, one possible solution is $$$a_1=qw$$$ and $$$a_2=q$$$.

In the third test case, one possible solution is $$$a_1=i$$$ and $$$a_2=o$$$.

In the fifth test case, one possible solution is $$$a_1=dokidokiliteratureclub$$$.

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 a multiset $$$S$$$ initially consisting of $$$n$$$ distinct non-negative integers. A multiset is a set, that can contain some elements multiple times.

You will perform the following operation $$$k$$$ times:

- Add the element $$$\lceil\frac{a+b}{2}\rceil$$$ (rounded up) into $$$S$$$, where $$$a = \operatorname{mex}(S)$$$ and $$$b = \max(S)$$$. If this number is already in the set, it is added again.

Here $$$\operatorname{max}$$$ of a multiset denotes the maximum integer in the multiset, and $$$\operatorname{mex}$$$ of a multiset denotes the smallest non-negative integer that is not present in the multiset. For example:

- $$$\operatorname{mex}(\{1,4,0,2\})=3$$$;
- $$$\operatorname{mex}(\{2,5,1\})=0$$$.

Your task is to calculate the number of distinct elements in $$$S$$$ after $$$k$$$ operations will be done.

## 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 of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1\le n\le 10^5$$$, $$$0\le k\le 10^9$$$) — the initial size of the multiset $$$S$$$ and how many operations you need to perform.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_i\le 10^9$$$) — the numbers in the initial multiset.

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

## Output Format
For each test case, print the number of distinct elements in $$$S$$$ after $$$k$$$ operations will be done.

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

## Note
In the first test case, $$$S=\{0,1,3,4\}$$$, $$$a=\operatorname{mex}(S)=2$$$, $$$b=\max(S)=4$$$, $$$\lceil\frac{a+b}{2}\rceil=3$$$. So $$$3$$$ is added into $$$S$$$, and $$$S$$$ becomes $$$\{0,1,3,3,4\}$$$. The answer is $$$4$$$.

In the second test case, $$$S=\{0,1,4\}$$$, $$$a=\operatorname{mex}(S)=2$$$, $$$b=\max(S)=4$$$, $$$\lceil\frac{a+b}{2}\rceil=3$$$. So $$$3$$$ is added into $$$S$$$, and $$$S$$$ becomes $$$\{0,1,3,4\}$$$. The answer 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
The $$$\text{$$$gcdSum$$$}$$$ of a positive integer is the $$$gcd$$$ of that integer with its sum of digits. Formally, $$$\text{$$$gcdSum$$$}(x) = gcd(x, \text{ sum of digits of } x)$$$ for a positive integer $$$x$$$. $$$gcd(a, b)$$$ denotes the greatest common divisor of $$$a$$$ and $$$b$$$ — the largest integer $$$d$$$ such that both integers $$$a$$$ and $$$b$$$ are divisible by $$$d$$$.

For example: $$$\text{$$$gcdSum$$$}(762) = gcd(762, 7 + 6 + 2)=gcd(762,15) = 3$$$.

Given an integer $$$n$$$, find the smallest integer $$$x \ge n$$$ such that $$$\text{$$$gcdSum$$$}(x) > 1$$$.

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

Then $$$t$$$ lines follow, each containing a single integer $$$n$$$ $$$(1 \le n \le 10^{18})$$$.

All test cases in one test are different.

## Output Format
Output $$$t$$$ lines, where the $$$i$$$-th line is a single integer containing the answer to the $$$i$$$-th test case.

## Examples
```input
3
11
31
75
```
```output
12
33
75
```

## Note
Let us explain the three test cases in the sample.

Test case 1: $$$n = 11$$$:

$$$\text{$$$gcdSum$$$}(11) = gcd(11, 1 + 1) = gcd(11,\ 2) = 1$$$.

$$$\text{$$$gcdSum$$$}(12) = gcd(12, 1 + 2) = gcd(12,\ 3) = 3$$$.

So the smallest number $$$\ge 11$$$ whose $$$gcdSum$$$ $$$> 1$$$ is $$$12$$$.

Test case 2: $$$n = 31$$$:

$$$\text{$$$gcdSum$$$}(31) = gcd(31, 3 + 1) = gcd(31,\ 4) = 1$$$.

$$$\text{$$$gcdSum$$$}(32) = gcd(32, 3 + 2) = gcd(32,\ 5) = 1$$$.

$$$\text{$$$gcdSum$$$}(33) = gcd(33, 3 + 3) = gcd(33,\ 6) = 3$$$.

So the smallest number $$$\ge 31$$$ whose $$$gcdSum$$$ $$$> 1$$$ is $$$33$$$.

Test case 3: $$$\ n = 75$$$:

$$$\text{$$$gcdSum$$$}(75) = gcd(75, 7 + 5) = gcd(75,\ 12) = 3$$$.

The $$$\text{$$$gcdSum$$$}$$$ of $$$75$$$ is already $$$> 1$$$. Hence, it is 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 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
Phoenix is playing with a new puzzle, which consists of $$$n$$$ identical puzzle pieces. Each puzzle piece is a right isosceles triangle as shown below.

A puzzle piece

The goal of the puzzle is to create a square using the $$$n$$$ pieces. He is allowed to rotate and move the pieces around, but none of them can overlap and all $$$n$$$ pieces must be used (of course, the square shouldn't contain any holes as well). Can he do it?

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the number of puzzle pieces.

## Output Format
For each test case, if Phoenix can create a square with the $$$n$$$ puzzle pieces, print YES. Otherwise, print NO.

## Examples
```input
3
2
4
6
```
```output
YES
YES
NO
```

## Note
For $$$n=2$$$, Phoenix can create a square like this:

For $$$n=4$$$, Phoenix can create a square like this:

For $$$n=6$$$, it is impossible for Phoenix to create a square.

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
Phoenix has $$$n$$$ blocks of height $$$h_1, h_2, \dots, h_n$$$, and all $$$h_i$$$ don't exceed some value $$$x$$$. He plans to stack all $$$n$$$ blocks into $$$m$$$ separate towers. The height of a tower is simply the sum of the heights of its blocks. For the towers to look beautiful, no two towers may have a height difference of strictly more than $$$x$$$.

Please help Phoenix build $$$m$$$ towers that look beautiful. Each tower must have at least one block and all blocks must be used.

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

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$x$$$ ($$$1 \le m \le n \le 10^5$$$; $$$1 \le x \le 10^4$$$) — the number of blocks, the number of towers to build, and the maximum acceptable height difference of any two towers, respectively.

The second line of each test case contains $$$n$$$ space-separated integers ($$$1 \le h_i \le x$$$) — the heights of the blocks.

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

## Output Format
For each test case, if Phoenix cannot build $$$m$$$ towers that look beautiful, print NO. Otherwise, print YES, followed by $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$, where $$$y_i$$$ ($$$1 \le y_i \le m$$$) is the index of the tower that the $$$i$$$-th block is placed in.

If there are multiple solutions, print any of them.

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

## Note
In the first test case, the first tower has height $$$1+2+3=6$$$ and the second tower has height $$$1+2=3$$$. Their difference is $$$6-3=3$$$ which doesn't exceed $$$x=3$$$, so the towers are beautiful.

In the second test case, the first tower has height $$$1$$$, the second tower has height $$$1+2=3$$$, and the third tower has height $$$3$$$. The maximum height difference of any two towers is $$$3-1=2$$$ which doesn't exceed $$$x=3$$$, so the towers are beautiful.

Now solve the problem and return the code.