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
Given an array $$$a$$$ of length $$$n$$$, containing integers. And there are two initially empty arrays $$$b$$$ and $$$c$$$. You need to add each element of array $$$a$$$ to exactly one of the arrays $$$b$$$ or $$$c$$$, in order to satisfy the following conditions:

- Both arrays $$$b$$$ and $$$c$$$ are non-empty. More formally, let $$$l_b$$$ be the length of array $$$b$$$, and $$$l_c$$$ be the length of array $$$c$$$. Then $$$l_b, l_c \ge 1$$$.
- For any two indices $$$i$$$ and $$$j$$$ ($$$1 \le i \le l_b, 1 \le j \le l_c$$$), $$$c_j$$$ is not a divisor of $$$b_i$$$.

Output the arrays $$$b$$$ and $$$c$$$ that can be obtained, or output $$$-1$$$ if they do not exist.

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

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

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

## Output Format
For each test case, output a single integer $$$-1$$$ if a solution does not exist.

Otherwise, in the first line, output two integers $$$l_b$$$ and $$$l_c$$$ — the lengths of arrays $$$b$$$ and $$$c$$$ respectively.

In the second line, output $$$l_b$$$ integers $$$b_1, b_2, \ldots, b_{l_b}$$$ — the elements of array $$$b$$$.

In the third line, output $$$l_c$$$ integers $$$c_1, c_2, \ldots, c_{l_c}$$$ — the elements of array $$$c$$$.

If there are multiple solutions, output any of them. You can output the elements of the arrays in any order.

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

## Note
In the first test case, a solution does not exist.

In the second test case, we can obtain $$$b = [1, 3, 5]$$$ and $$$c = [2, 4]$$$. Then elements $$$2$$$ and $$$4$$$ do not divide elements $$$1, 3$$$ and $$$5$$$.

In the fifth test case, we can obtain $$$b = [4, 8, 4]$$$ and $$$c = [12, 12]$$$.

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
Artem suggested a game to the girl Olya. There is a list of $$$n$$$ arrays, where the $$$i$$$-th array contains $$$m_i \ge 2$$$ positive integers $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m_i}$$$.

Olya can move at most one (possibly $$$0$$$) integer from each array to another array. Note that integers can be moved from one array only once, but integers can be added to one array multiple times, and all the movements are done at the same time.

The beauty of the list of arrays is defined as the sum $$$\sum_{i=1}^n \min_{j=1}^{m_i} a_{i,j}$$$. In other words, for each array, we find the minimum value in it and then sum up these values.

The goal of the game is to maximize the beauty of the list of arrays. Help Olya win this challenging game!

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 25000$$$) — the number of arrays in the list.

This is followed by descriptions of the arrays. Each array description consists of two lines.

The first line contains a single integer $$$m_i$$$ ($$$2 \le m_i \le 50000$$$) — the number of elements in the $$$i$$$-th array.

The next line contains $$$m_i$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m_i}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — the elements of the $$$i$$$-th array.

It is guaranteed that the sum of $$$m_i$$$ over all test cases does not exceed $$$50000$$$.

## Output Format
For each test case, output a single line containing a single integer — the maximum beauty of the list of arrays that Olya can achieve.

## Examples
```input
3
2
2
1 2
2
4 3
1
3
100 1 6
3
4
1001 7 1007 5
3
8 11 6
2
2 9
```
```output
5
1
19
```

## Note
In the first test case, we can move the integer $$$3$$$ from the second array to the first array. Then the beauty is $$$\min(1, 2, 3) + \min(4) = 5$$$. It can be shown that this is the maximum possible beauty.

In the second test case, there is only one array, so regardless of the movements, the beauty will be $$$\min(100, 1, 6) = 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 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Andrey is just starting to come up with problems, and it's difficult for him. That's why he came up with a strange problem about permutations$$$^{\dagger}$$$ and asks you to solve it. Can you do it?

Let's call the cost of a permutation $$$p$$$ of length $$$n$$$ the value of the expression:

$$$(\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)$$$.

Find the maximum cost among all permutations of length $$$n$$$.

$$$^{\dagger}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

The only line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 250$$$) — the length of the permutation.

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

## Output Format
For each test case, output a single integer — the maximum cost among all permutations of length $$$n$$$.

## Examples
```input
5
2
4
3
10
20
```
```output
2
17
7
303
2529
```

## Note
In the first test case, the permutation with the maximum cost is $$$[2, 1]$$$. The cost is equal to $$$2 \cdot 1 + 1 \cdot 2 - \max (2 \cdot 1, 1 \cdot 2)= 2 + 2 - 2 = 2$$$.

In the second test case, the permutation with the maximum cost is $$$[1, 2, 4, 3]$$$. The cost is equal to $$$1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17$$$.

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.5 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a$$$ of length $$$n$$$ and an array $$$b$$$ of length $$$n$$$. The cost of a segment $$$[l, r]$$$, $$$1 \le l \le r \le n$$$, is defined as $$$|b_l - a_r| + |b_r - a_l|$$$.

Recall that two segments $$$[l_1, r_1]$$$, $$$1 \le l_1 \le r_1 \le n$$$, and $$$[l_2, r_2]$$$, $$$1 \le l_2 \le r_2 \le n$$$, are non-intersecting if one of the following conditions is satisfied: $$$r_1 < l_2$$$ or $$$r_2 < l_1$$$.

The length of a segment $$$[l, r]$$$, $$$1 \le l \le r \le n$$$, is defined as $$$r - l + 1$$$.

Find the maximum possible sum of costs of non-intersecting segments $$$[l_j, r_j]$$$, $$$1 \le l_j \le r_j \le n$$$, whose total length is equal to $$$k$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3000$$$) — the length of array $$$a$$$ and the total length of segments.

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

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — the elements of array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test case does not exceed $$$3000$$$.

## Output Format
For each test case, output a single number — the maximum possible sum of costs of such segments.

## Examples
```input
5
4 4
1 1 1 1
1 1 1 1
3 2
1 3 2
5 2 3
5 1
1 2 3 4 5
1 2 3 4 5
7 2
1 3 7 6 4 7 2
1 5 3 2 7 4 5
4 2
17 3 5 8
16 2 5 9
```
```output
0
10
0
16
28
```

## Note
In the first test case, the cost of any segment is $$$0$$$, so the total cost is $$$0$$$.

In the second test case, we can take the segment $$$[1, 1]$$$ with a cost of $$$8$$$ and the segment $$$[3, 3]$$$ with a cost of $$$2$$$ to get a total sum of $$$10$$$. It can be shown that this is the optimal solution.

In the third test case, we are only interested in segments of length $$$1$$$, and the cost of any such segment is $$$0$$$.

In the fourth test case, it can be shown that the optimal sum is $$$16$$$. For example, we can take the segments $$$[3, 3]$$$ and $$$[4, 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 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
Jellyfish has $$$n$$$ green apple pieces. Each green apple piece weighs $$$1~\text{kg}$$$. Jellyfish wants to divide these green apple pieces equally among $$$m$$$ people.

Jellyfish has a magic knife. Each time Jellyfish can choose one piece of green apple and divide it into two smaller pieces, with each piece having half the weight of the original piece.

Jellyfish wants to know the minimum number of operations needed such that she can divide the green apple pieces such that the total weight of apple pieces received by each person is the same.

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

The first and only line of each test case contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^9$$$) — the number of the green apple pieces initially and the number of the people.

## Output Format
For each test case, output a single integer — the minimum number of operations required to divide all the green apples equally among the $$$m$$$ people. If this cannot be achieved using a finite number of operations, output $$$-1$$$ instead.

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

## Note
In the first test case, we do not need to divide the apple pieces. Each person will receive $$$2$$$ pieces of $$$1~\text{kg}$$$ and the total weight of apple pieces received by each person is $$$2~\text{kg}$$$.

In the second test case, it is impossible to divide the apple equally using a finite number of operations.

In the third test case, we can divide two of the apple pieces of weight $$$1~\text{kg}$$$, getting $$$4$$$ apple pieces of weight $$$0.5~\text{kg}$$$. Each person will receive $$$1$$$ apple piece of weight $$$0.5~\text{kg}$$$ and $$$2$$$ apple pieces of weight $$$1~\text{kg}$$$. The total weight of apple pieces received by each person is $$$2.5~\text{kg}$$$.

In the fourth test case, we first divide all $$$3$$$ of the apple pieces of weight $$$1~\text{kg}$$$, getting $$$6$$$ pieces of weight $$$0.5~\text{kg}$$$. Then, we further divide two of the apple pieces of weight $$$0.5~\text{kg}$$$, getting $$$4$$$ pieces of weight $$$0.25~\text{kg}$$$. Each person will receive $$$1$$$ apple piece of weight $$$0.5~\text{kg}$$$ and $$$1$$$ apple piece of weight $$$0.25~\text{kg}$$$. The total weight of apples received by each person is $$$0.75~\text{kg}$$$.

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 an array of $$$n$$$ nonnegative integers $$$a_1, a_2, \dots, a_n$$$.

Let $$$m$$$ be a variable that is initialized to $$$0$$$, Jellyfish will perform the following operation $$$n$$$ times:

- select an index $$$i$$$ ($$$1 \leq i \leq |a|$$$) and delete $$$a_i$$$ from $$$a$$$.
- add $$$\operatorname{MEX}(a)^{\dagger}$$$ to $$$m$$$.

Now Jellyfish wants to know the minimum possible final value of $$$m$$$ if he performs all the operations optimally.

$$$^{\dagger}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

- The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
- The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
- The MEX of $$$[0,3,1,2]$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not.

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

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

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

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

## Output Format
For each test case, output a single integer — the minimum value of $$$m$$$ if the operations are performed optimally.

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

## Note
In the first test case, we delete elements from $$$a$$$ in the following order: $$$[5,2,\color{red}{1},0,3,0,4,0] \to [5,2,0,3,\color{red}{0},4,0] \to [5,2,\color{red}{0},3,4,0] \to [5,2,3,4,\color{red}{0}] \to [5,2,\color{red}{3},4] \to [\color{red}{5},2,4] \to [\color{red}{2},4] \to [\color{red}{4}] \to [~]$$$. The value of $$$m$$$ will be $$$1+1+1+0+0+0+0+0=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 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 positive integer is called $$$k$$$-beautiful, if the digit sum of the decimal representation of this number is divisible by $$$k^{\dagger}$$$. For example, $$$9272$$$ is $$$5$$$-beautiful, since the digit sum of $$$9272$$$ is $$$9 + 2 + 7 + 2 = 20$$$.

You are given two integers $$$x$$$ and $$$k$$$. Please find the smallest integer $$$y \ge x$$$ which is $$$k$$$-beautiful.

$$$^{\dagger}$$$ An integer $$$n$$$ is divisible by $$$k$$$ if there exists an integer $$$m$$$ such that $$$n = k \cdot m$$$.

## 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 only line of each test case contains two integers $$$x$$$ and $$$k$$$ ($$$1 \le x \le 10^9$$$, $$$1 \le k \le 10$$$).

## Output Format
For each test case, output the smallest integer $$$y \ge x$$$ which is $$$k$$$-beautiful.

## Examples
```input
6
1 5
10 8
37 9
777 3
1235 10
1 10
```
```output
5
17
45
777
1243
19
```

## Note
In the first test case, numbers from $$$1$$$ to $$$4$$$ consist of a single digit, thus the digit sum is equal to the number itself. None of the integers from $$$1$$$ to $$$4$$$ are divisible by $$$5$$$.

In the fourth test case, the digit sum of $$$777$$$ is $$$7 + 7 + 7 = 21$$$ which is already divisible by $$$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 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
The array $$$a_1, a_2, \ldots, a_m$$$ is initially filled with zeroes. You are given $$$n$$$ pairwise distinct segments $$$1 \le l_i \le r_i \le m$$$. You have to select an arbitrary subset of these segments (in particular, you may select an empty set). Next, you do the following:

- For each $$$i = 1, 2, \ldots, n$$$, if the segment $$$(l_i, r_i)$$$ has been selected to the subset, then for each index $$$l_i \le j \le r_i$$$ you increase $$$a_j$$$ by $$$1$$$ (i. e. $$$a_j$$$ is replaced by $$$a_j + 1$$$). If the segment $$$(l_i, r_i)$$$ has not been selected, the array does not change.
- Next (after processing all values of $$$i = 1, 2, \ldots, n$$$), you compute $$$\max(a)$$$ as the maximum value among all elements of $$$a$$$. Analogously, compute $$$\min(a)$$$ as the minimum value.
- Finally, the cost of the selected subset of segments is declared as $$$\max(a) - \min(a)$$$.

Please, find the maximum cost among all subsets of segments.

## 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 two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$) — the number of segments and the length of the array.

The following $$$n$$$ lines of each test case describe the segments. The $$$i$$$-th of these lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$). It is guaranteed that the segments are pairwise distinct.

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, output the maximum cost among all subsets of the given set of segments.

## Examples
```input
6
1 3
2 2
3 8
2 4
3 5
4 6
6 3
1 1
1 2
1 3
2 2
2 3
3 3
7 6
2 2
1 6
1 2
5 6
1 5
4 4
3 6
6 27
6 26
5 17
2 3
20 21
1 22
12 24
4 1000000000
2 999999999
3 1000000000
123456789 987654321
9274 123456789
```
```output
1
3
2
3
4
4
```

## Note
In the first test case, there is only one segment available. If we do not select it, then the array will be $$$a = [0, 0, 0]$$$, and the cost of such (empty) subset of segments will be $$$0$$$. If, however, we select the only segment, the array will be $$$a = [0, 1, 0]$$$, and the cost will be $$$1 - 0 = 1$$$.

In the second test case, we can select all the segments: the array will be $$$a = [0, 1, 2, 3, 2, 1, 0, 0]$$$ in this case. The cost will be $$$3 - 0 = 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 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 of integers $$$a_1, a_2, \ldots, a_n$$$.

A pair of integers $$$(i, j)$$$, such that $$$1 \le i < j \le n$$$, is called good, if there does not exist an integer $$$k$$$ ($$$1 \le k \le n$$$) such that $$$a_i$$$ is divisible by $$$a_k$$$ and $$$a_j$$$ is divisible by $$$a_k$$$ at the same time.

Please, find the number of good pairs.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 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 10^6$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

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

## Output Format
For each test case, output the number of good pairs.

## Examples
```input
6
4
2 4 4 4
4
2 3 4 4
9
6 8 9 4 6 8 9 4 9
9
7 7 4 4 9 9 6 2 9
18
10 18 18 15 14 4 5 6 8 9 10 12 15 16 18 17 13 11
21
12 19 19 18 18 12 2 18 19 12 12 3 12 12 12 18 19 16 18 19 12
```
```output
0
3
26
26
124
82
```

## Note
In the first test case, there are no good pairs.

In the second test case, here are all the good pairs: $$$(1, 2)$$$, $$$(2, 3)$$$, and $$$(2, 4)$$$.

Now solve the problem and return the code.