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
William has array of $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. He can perform the following sequence of operations any number of times:

1. Pick any two items from array $$$a_i$$$ and $$$a_j$$$, where $$$a_i$$$ must be a multiple of $$$2$$$
2. $$$a_i = \frac{a_i}{2}$$$
3. $$$a_j = a_j \cdot 2$$$

Help William find the maximal sum of array elements, which he can get by performing the sequence of operations described above.

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

The first line of each test case contains an integer $$$n$$$ $$$(1 \le n \le 15)$$$, the number of elements in William's array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i < 16)$$$, the contents of William's array.

## Output Format
For each test case output the maximal sum of array elements after performing an optimal sequence of operations.

## Examples
```input
5
3
6 4 2
5
1 2 3 4 5
1
10
3
2 3 4
15
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
```
```output
50
46
10
26
35184372088846
```

## Note
In the first example test case the optimal sequence would be:

1. Pick $$$i = 2$$$ and $$$j = 1$$$. After performing a sequence of operations $$$a_2 = \frac{4}{2} = 2$$$ and $$$a_1 = 6 \cdot 2 = 12$$$, making the array look as: [12, 2, 2].
2. Pick $$$i = 2$$$ and $$$j = 1$$$. After performing a sequence of operations $$$a_2 = \frac{2}{2} = 1$$$ and $$$a_1 = 12 \cdot 2 = 24$$$, making the array look as: [24, 1, 2].
3. Pick $$$i = 3$$$ and $$$j = 1$$$. After performing a sequence of operations $$$a_3 = \frac{2}{2} = 1$$$ and $$$a_1 = 24 \cdot 2 = 48$$$, making the array look as: [48, 1, 1].

The final answer $$$48 + 1 + 1 = 50$$$.

In the third example test case there is no way to change the sum of elements, so the answer is $$$10$$$.

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
William arrived at a conference dedicated to cryptocurrencies. Networking, meeting new people, and using friends' connections are essential to stay up to date with the latest news from the world of cryptocurrencies.

The conference has $$$n$$$ participants, who are initially unfamiliar with each other. William can introduce any two people, $$$a$$$ and $$$b$$$, who were not familiar before, to each other.

William has $$$d$$$ conditions, $$$i$$$'th of which requires person $$$x_i$$$ to have a connection to person $$$y_i$$$. Formally, two people $$$x$$$ and $$$y$$$ have a connection if there is such a chain $$$p_1=x, p_2, p_3, \dots, p_k=y$$$ for which for all $$$i$$$ from $$$1$$$ to $$$k - 1$$$ it's true that two people with numbers $$$p_i$$$ and $$$p_{i + 1}$$$ know each other.

For every $$$i$$$ ($$$1 \le i \le d$$$) William wants you to calculate the maximal number of acquaintances one person can have, assuming that William satisfied all conditions from $$$1$$$ and up to and including $$$i$$$ and performed exactly $$$i$$$ introductions. The conditions are being checked after William performed $$$i$$$ introductions. The answer for each $$$i$$$ must be calculated independently. It means that when you compute an answer for $$$i$$$, you should assume that no two people have been introduced to each other yet.

## Input Format
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$2 \le n \le 10^3, 1 \le d \le n - 1$$$), the number of people, and number of conditions, respectively.

Each of the next $$$d$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n, x_i \neq y_i$$$), the numbers of people which must have a connection according to condition $$$i$$$.

## Output Format
Output $$$d$$$ integers. $$$i$$$th number must equal the number of acquaintances the person with the maximal possible acquaintances will have, if William performed $$$i$$$ introductions and satisfied the first $$$i$$$ conditions.

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

## Note
The explanation for the first test case:

In this explanation, the circles and the numbers in them denote a person with the corresponding number. The line denotes that William introduced two connected people. The person marked with red has the most acquaintances. These are not the only correct ways to introduce people.

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

# Problem
William has two arrays of numbers $$$a_1, a_2, \dots, a_n$$$ and $$$b_1, b_2, \dots, b_m$$$. The arrays satisfy the conditions of being convex. Formally an array $$$c$$$ of length $$$k$$$ is considered convex if $$$c_i - c_{i - 1} < c_{i + 1} - c_i$$$ for all $$$i$$$ from $$$2$$$ to $$$k - 1$$$ and $$$c_1 < c_2$$$.

Throughout William's life he observed $$$q$$$ changes of two types happening to the arrays:

1. Add the arithmetic progression $$$d, d \cdot 2, d \cdot 3, \dots, d \cdot k$$$ to the suffix of the array $$$a$$$ of length $$$k$$$. The array after the change looks like this: $$$[a_1, a_2, \dots, a_{n - k}, a_{n - k + 1} + d, a_{n - k + 2} + d \cdot 2, \dots, a_n + d \cdot k]$$$.
2. The same operation, but for array $$$b$$$.

After each change a matrix $$$d$$$ is created from arrays $$$a$$$ and $$$b$$$, of size $$$n \times m$$$, where $$$d_{i, j}=a_i + b_j$$$. William wants to get from cell ($$$1, 1$$$) to cell ($$$n, m$$$) of this matrix. From cell ($$$x, y$$$) he can only move to cells ($$$x + 1, y$$$) and ($$$x, y + 1$$$). The length of a path is calculated as the sum of numbers in cells visited by William, including the first and the last cells.

After each change William wants you to help find out the minimal length of the path he could take.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$2 \le n \le 100, 2 \le m \le 10^5$$$, $$$1 \le q \le 10^5$$$), the sizes of the arrays and the number of changes.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$), the contents of array $$$a$$$.

The third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^{12}$$$), the contents of array $$$b$$$.

Each of the next $$$q$$$ lines contains three integers $$$type$$$, $$$k$$$ and $$$d$$$ ($$$1 \le type \le 2$$$, if $$$type = 1$$$, then $$$1 \le k \le n$$$ otherwise $$$1 \le k \le m$$$, $$$1 \le d \le 10^3$$$).

## Output Format
After each change, output one integer, the minimum length of the path in the constructed matrix.

## Examples
```input
5 3 4
1 2 4 7 11
5 7 10
1 3 2
2 2 5
1 5 4
2 1 7
```
```output
98
128
219
229
```
-----
```input
5 6 7
4 9 22 118 226
7 94 238 395 565 738
2 1 95
1 4 54
1 2 5
1 2 87
2 6 62
2 1 143
1 1 77
```
```output
3639
5122
5162
5617
7663
7806
7960
```

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: 512.0 MB

# Problem
You are given an undirected graph of $$$n$$$ vertices indexed from $$$1$$$ to $$$n$$$, where vertex $$$i$$$ has a value $$$a_i$$$ assigned to it and all values $$$a_i$$$ are different. There is an edge between two vertices $$$u$$$ and $$$v$$$ if either $$$a_u$$$ divides $$$a_v$$$ or $$$a_v$$$ divides $$$a_u$$$.

Find the minimum number of vertices to remove such that the remaining graph is bipartite, when you remove a vertex you remove all the edges incident to it.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5\cdot10^4$$$) — the number of vertices in the graph.

The second line of each test case contains $$$n$$$ integers, the $$$i$$$-th of them is the value $$$a_i$$$ ($$$1 \le a_i \le 5\cdot10^4$$$) assigned to the $$$i$$$-th vertex, all values $$$a_i$$$ are different.

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

## Output Format
For each test case print a single integer — the minimum number of vertices to remove such that the remaining graph is bipartite.

## Examples
```input
4
4
8 4 2 1
4
30 2 3 5
5
12 4 6 2 3
10
85 195 5 39 3 13 266 154 14 2
```
```output
2
0
1
2
```

## Note
In the first test case if we remove the vertices with values $$$1$$$ and $$$2$$$ we will obtain a bipartite graph, so the answer is $$$2$$$, it is impossible to remove less than $$$2$$$ vertices and still obtain a bipartite graph.

BeforeAfter test case #1

In the second test case we do not have to remove any vertex because the graph is already bipartite, so the answer is $$$0$$$.

BeforeAfter test case #2

In the third test case we only have to remove the vertex with value $$$12$$$, so the answer is $$$1$$$.

BeforeAfter test case #3

In the fourth test case we remove the vertices with values $$$2$$$ and $$$195$$$, so the answer is $$$2$$$.

BeforeAfter test case #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
You are given a string $$$s$$$ of length $$$n$$$ and a number $$$k$$$. Let's denote by $$$rev(s)$$$ the reversed string $$$s$$$ (i.e. $$$rev(s) = s_n s_{n-1} ... s_1$$$). You can apply one of the two kinds of operations to the string:

- replace the string $$$s$$$ with $$$s + rev(s)$$$
- replace the string $$$s$$$ with $$$rev(s) + s$$$

How many different strings can you get as a result of performing exactly $$$k$$$ operations (possibly of different kinds) on the original string $$$s$$$?

In this statement we denoted the concatenation of strings $$$s$$$ and $$$t$$$ as $$$s + t$$$. In other words, $$$s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m$$$, where $$$n$$$ and $$$m$$$ are the lengths of strings $$$s$$$ and $$$t$$$ respectively.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — number of test cases. Next $$$2 \cdot t$$$ lines contain $$$t$$$ test cases:

The first line of a test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le 1000$$$) — the length of the string and the number of operations respectively.

The second string of a test case contains one string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters.

## Output Format
For each test case, print the answer (that is, the number of different strings that you can get after exactly $$$k$$$ operations) on a separate line.

It can be shown that the answer does not exceed $$$10^9$$$ under the given constraints.

## Examples
```input
4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab
```
```output
2
2
1
1
```

## Note
In the first test case of the example:

After the first operation the string $$$s$$$ can become either aabbaa or baaaab. After the second operation there are 2 possibilities for $$$s$$$: aabbaaaabbaa and baaaabbaaaab.

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 work for a well-known department store that uses leading technologies and employs mechanistic work — that is, robots!

The department you work in sells $$$n \cdot k$$$ items. The first item costs $$$1$$$ dollar, the second item costs $$$2$$$ dollars, and so on: $$$i$$$-th item costs $$$i$$$ dollars. The items are situated on shelves. The items form a rectangular grid: there are $$$n$$$ shelves in total, and each shelf contains exactly $$$k$$$ items. We will denote by $$$a_{i,j}$$$ the price of $$$j$$$-th item (counting from the left) on the $$$i$$$-th shelf, $$$1 \le i \le n, 1 \le j \le k$$$.

Occasionally robots get curious and ponder on the following question: what is the mean price (arithmetic average) of items $$$a_{i,l}, a_{i,l+1}, \ldots, a_{i,r}$$$ for some shelf $$$i$$$ and indices $$$l \le r$$$? Unfortunately, the old robots can only work with whole numbers. If the mean price turns out not to be an integer, they break down.

You care about robots' welfare. You want to arrange the items in such a way that the robots cannot theoretically break. Formally, you want to choose such a two-dimensional array $$$a$$$ that:

- Every number from $$$1$$$ to $$$n \cdot k$$$ (inclusively) occurs exactly once.
- For each $$$i, l, r$$$, the mean price of items from $$$l$$$ to $$$r$$$ on $$$i$$$-th shelf is an integer.

Find out if such an arrangement is possible, and if it is, give any example of such arrangement.

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 500$$$) — the number of shelves and length of each shelf, respectively.

It is guaranteed that the sum $$$n$$$ over all test cases does not exceed $$$500$$$ and the sum $$$k$$$ over all test cases does not exceed $$$500$$$.

## Output Format
Print the answer for each test case.

If such an arrangement exists, print "YES" on a single line. After that, print any example on $$$n$$$ lines of $$$k$$$ numbers each, one line per shelf. Each number from $$$1$$$ to $$$n \cdot k$$$ must occur exactly once in the output.

If no good arrangement exists, print a single word "NO" on its own line.

## Examples
```input
4
1 1
2 2
3 3
3 1
```
```output
YES
1 
YES
1 3 
2 4 
NO
YES
1 
2 
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: 1.5 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$m$$$ arrays of positive integers. Each array is of even length.

You need to split all these integers into two equal multisets $$$L$$$ and $$$R$$$, that is, each element of each array should go into one of two multisets (but not both). Additionally, for each of the $$$m$$$ arrays, exactly half of its elements should go into $$$L$$$, and the rest should go into $$$R$$$.

Give an example of such a division or determine that no such division exists.

## Input Format
The first line contains an integer $$$m$$$ ($$$1 \le m \le 10 ^ 5$$$) — the number of arrays.

The next $$$2 \cdot m$$$ lines contain descriptions of the arrays.

For each array, the first line contains an even integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10 ^ 5$$$) — the length of the array. The second line consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10 ^ 9$$$) — array elements.

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

## Output Format
If the answer exists, print "YES", and then print $$$m$$$ lines.

On each line, for each element, print the letter "L" or "R" (capitalized, without spaces), depending on which multiset the element should go into.

If there is no answer, print "NO" on the only line.

## Examples
```input
3
2
1 2
4
1 2 3 3
6
1 1 2 2 3 3
```
```output
YES
RL
LRLR
RLLRRL
```

## Note
In the first array, we add the first element to $$$R$$$ and the second to $$$L$$$. Now $$$L = \{2\}$$$, and $$$R = \{1\}$$$.

In the second array, we add the first and third elements to $$$L$$$ and the rest to $$$R$$$. Now $$$L = \{1, 2, 3\}$$$ and $$$R = \{1, 2, 3\}$$$.

In the third array, we add elements 2, 3, and 6 to $$$L$$$, and others — to $$$R$$$. As a result, $$$L = R = \{1, 1, 2, 2, 3, 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
Sam is a kindergartener, and there are $$$n$$$ children in his group. He decided to create a team with some of his children to play "brawl:go 2".

Sam has $$$n$$$ power-ups, the $$$i$$$-th has type $$$a_i$$$. A child's strength is equal to the number of different types among power-ups he has.

For a team of size $$$k$$$, Sam will distribute all $$$n$$$ power-ups to $$$k$$$ children in such a way that each of the $$$k$$$ children receives at least one power-up, and each power-up is given to someone.

For each integer $$$k$$$ from $$$1$$$ to $$$n$$$, find the minimum sum of strengths of a team of $$$k$$$ children Sam can get.

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — types of Sam's power-ups.

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

## Output Format
For every test case print $$$n$$$ integers.

The $$$k$$$-th integer should be equal to the minimum sum of strengths of children in the team of size $$$k$$$ that Sam can get.

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

## Note
One of the ways to give power-ups to minimise the sum of strengths in the first test case:

- $$$k = 1: \{1, 1, 2\}$$$
- $$$k = 2: \{1, 1\}, \{2\}$$$
- $$$k = 3: \{1\}, \{1\}, \{2\}$$$

One of the ways to give power-ups to minimise the sum of strengths in the second test case:

- $$$k = 1: \{1, 2, 2, 2, 4, 5\}$$$
- $$$k = 2: \{2, 2, 2, 4, 5\}, \{1\}$$$
- $$$k = 3: \{2, 2, 2, 5\}, \{1\}, \{4\}$$$
- $$$k = 4: \{2, 2, 2\}, \{1\}, \{4\}, \{5\}$$$
- $$$k = 5: \{2, 2\}, \{1\}, \{2\}, \{4\}, \{5\}$$$
- $$$k = 6: \{1\}, \{2\}, \{2\}, \{2\}, \{4\}, \{5\}$$$

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_1, a_2, \ldots, a_n$$$ of positive integers. A good pair is a pair of indices $$$(i, j)$$$ with $$$1 \leq i, j \leq n$$$ such that, for all $$$1 \leq k \leq n$$$, the following equality holds:

$$$$$$ |a_i - a_k| + |a_k - a_j| = |a_i - a_j|, $$$$$$ where $$$|x|$$$ denotes the absolute value of $$$x$$$.

Find a good pair. Note that $$$i$$$ can be equal to $$$j$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) where $$$a_i$$$ is the $$$i$$$-th element of the array.

The sum of $$$n$$$ for all test cases is at most $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single line with two space-separated indices $$$i$$$ and $$$j$$$ which form a good pair of the array. The case $$$i=j$$$ is allowed. It can be shown that such a pair always exists. If there are multiple good pairs, print any of them.

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

## Note
In the first case, for $$$i = 2$$$ and $$$j = 3$$$ the equality holds true for all $$$k$$$:

- $$$k = 1$$$: $$$|a_2 - a_1| + |a_1 - a_3| = |2 - 5| + |5 - 7| = 5 = |2 - 7| = |a_2-a_3|$$$,
- $$$k = 2$$$: $$$|a_2 - a_2| + |a_2 - a_3| = |2 - 2| + |2 - 7| = 5 = |2 - 7| = |a_2-a_3|$$$,
- $$$k = 3$$$: $$$|a_2 - a_3| + |a_3 - a_3| = |2 - 7| + |7 - 7| = 5 = |2 - 7| = |a_2-a_3|$$$.

Now solve the problem and return the code.