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

# Problem
The row-major order of an $$$r \times c$$$ grid of characters $$$A$$$ is the string obtained by concatenating all the rows, i.e. $$$$$$ A_{11}A_{12} \dots A_{1c}A_{21}A_{22} \dots A_{2c} \dots A_{r1}A_{r2} \dots A_{rc}. $$$$$$

A grid of characters $$$A$$$ is bad if there are some two adjacent cells (cells sharing an edge) with the same character.

You are given a positive integer $$$n$$$. Consider all strings $$$s$$$ consisting of only lowercase Latin letters such that they are not the row-major order of any bad grid. Find any string with the minimum number of distinct characters among all such strings of length $$$n$$$.

It can be proven that at least one such string exists under the constraints of the problem.

## 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 a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

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

## Output Format
For each test case, output a string with the minimum number of distinct characters among all suitable strings of length $$$n$$$.

If there are multiple solutions, print any of them.

## Examples
```input
4
4
2
1
6
```
```output
that
is
a
tomato
```

## Note
In the first test case, there are $$$3$$$ ways $$$s$$$ can be the row-major order of a grid, and they are all not bad: tththathatat It can be proven that $$$3$$$ distinct characters is the minimum possible.

In the second test case, there are $$$2$$$ ways $$$s$$$ can be the row-major order of a grid, and they are both not bad: iiss It can be proven that $$$2$$$ distinct characters is the minimum possible.

In the third test case, there is only $$$1$$$ way $$$s$$$ can be the row-major order of a grid, and it is not bad.

In the fourth test case, there are $$$4$$$ ways $$$s$$$ can be the row-major order of a grid, and they are all not bad: ttotomtomatoomaatomtoato It can be proven that $$$4$$$ distinct characters is the minimum possible. Note that, for example, the string "orange" is not an acceptable output because it has $$$6 > 4$$$ distinct characters, and the string "banana" is not an acceptable output because it is the row-major order of the following bad grid: banana

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

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

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

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between this problem and the easy version is the constraints on $$$t$$$ and $$$n$$$.

You are given an array of $$$n$$$ positive integers $$$a_1,\dots,a_n$$$, and a (possibly negative) integer $$$c$$$.

Across all permutations $$$b_1,\dots,b_n$$$ of the array $$$a_1,\dots,a_n$$$, consider the minimum possible value of $$$$$$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|.$$$$$$ Find the lexicographically smallest permutation $$$b$$$ of the array $$$a$$$ that achieves this minimum.

A sequence $$$x$$$ is lexicographically smaller than a sequence $$$y$$$ if and only if one of the following holds:

- $$$x$$$ is a prefix of $$$y$$$, but $$$x \ne y$$$;
- in the first position where $$$x$$$ and $$$y$$$ differ, the sequence $$$x$$$ has a smaller element than the corresponding element in $$$y$$$.

## 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 $$$c$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$-10^9 \le c \le 10^9$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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 $$$n$$$ integers $$$b_1,\dots,b_n$$$, the lexicographically smallest permutation of $$$a$$$ that achieves the minimum $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$.

## Examples
```input
3
6 -7
3 1 4 1 5 9
3 2
1 3 5
1 2718
2818
```
```output
9 3 1 4 5 1
1 3 5
2818
```

## Note
In the first test case, it can be proven that the minimum possible value of $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ is $$$27$$$, and the permutation $$$b = [9,3,1,4,5,1]$$$ is the lexicographically smallest permutation of $$$a$$$ that achieves this minimum: $$$|3-9-(-7)|+|1-3-(-7)|+|4-1-(-7)|+|5-4-(-7)|+|1-5-(-7)| = 1+5+10+8+3 = 27$$$.

In the second test case, the minimum possible value of $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ is $$$0$$$, and $$$b = [1,3,5]$$$ is the lexicographically smallest permutation of $$$a$$$ that achieves this.

In the third test case, there is only one permutation $$$b$$$.

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

# Problem
You are given a tree with $$$n$$$ nodes labelled $$$1,2,\dots,n$$$. The $$$i$$$-th edge connects nodes $$$u_i$$$ and $$$v_i$$$ and has an unknown positive integer weight $$$w_i$$$. To help you figure out these weights, you are also given the distance $$$d_i$$$ between the nodes $$$i$$$ and $$$i+1$$$ for all $$$1 \le i \le n-1$$$ (the sum of the weights of the edges on the simple path between the nodes $$$i$$$ and $$$i+1$$$ in the tree).

Find the weight of each edge. If there are multiple solutions, print any of them. If there are no weights $$$w_i$$$ consistent with the information, print a single integer $$$-1$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$).

The last line contains $$$n-1$$$ integers $$$d_1,\dots,d_{n-1}$$$ ($$$1 \le d_i \le 10^{12}$$$).

It is guaranteed that the given edges form a tree.

## Output Format
If there is no solution, print a single integer $$$-1$$$. Otherwise, output $$$n-1$$$ lines containing the weights $$$w_1,\dots,w_{n-1}$$$.

If there are multiple solutions, print any of them.

## Examples
```input
5
1 2
1 3
2 4
2 5
31 41 59 26
```
```output
31
10
18
8
```
-----
```input
3
1 2
1 3
18 18
```
```output
-1
```
-----
```input
9
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 2
236 205 72 125 178 216 214 117
```
```output
31
41
59
26
53
58
97
93
```

## Note
In the first sample, the tree is as follows:

In the second sample, note that $$$w_2$$$ is not allowed to be $$$0$$$ because it must be a positive integer, so there is no solution.

In the third sample, the tree is as follows:

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

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

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

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
An array $$$a_1,\dots,a_n$$$ of length $$$n$$$ is initially all blank. There are $$$n$$$ updates where one entry of $$$a$$$ is updated to some number, such that $$$a$$$ becomes a permutation of $$$1,2,\dots,n$$$ after all the updates.

After each update, find the number of ways (modulo $$$998\,244\,353$$$) to fill in the remaining blank entries of $$$a$$$ so that $$$a$$$ becomes a permutation of $$$1,2,\dots,n$$$ and all cycle lengths in $$$a$$$ are multiples of $$$3$$$.

A permutation of $$$1,2,\dots,n$$$ is an array of length $$$n$$$ consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. A cycle in a permutation $$$a$$$ is a sequence of pairwise distinct integers $$$(i_1,\dots,i_k)$$$ such that $$$i_2 = a_{i_1},i_3 = a_{i_2},\dots,i_k = a_{i_{k-1}},i_1 = a_{i_k}$$$. The length of this cycle is the number $$$k$$$, which is a multiple of $$$3$$$ if and only if $$$k \equiv 0 \pmod 3$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$, $$$n \equiv 0 \pmod 3$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$, representing that the $$$i$$$-th update changes $$$a_{x_i}$$$ to $$$y_i$$$.

It is guaranteed that $$$x_1,\dots,x_n$$$ and $$$y_1,\dots,y_n$$$ are permutations of $$$1,2,\dots,n$$$, i.e. $$$a$$$ becomes a permutation of $$$1,2,\dots,n$$$ after all the updates.

## Output Format
Output $$$n$$$ lines: the number of ways (modulo $$$998\,244\,353$$$) after the first $$$1,2,\dots,n$$$ updates.

## Examples
```input
6
3 2
1 4
4 5
2 6
5 1
6 3
```
```output
32
8
3
2
1
1
```
-----
```input
3
1 1
2 3
3 2
```
```output
0
0
0
```
-----
```input
18
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1
```
```output
671571067
353924552
521242461
678960117
896896000
68992000
6272000
627200
62720
7840
1120
160
32
8
2
1
1
1
```

## Note
In the first sample, for example, after the $$$3$$$rd update the $$$3$$$ ways to complete the permutation $$$a = [4,\_,2,5,\_,\_]$$$ are as follows:

- $$$[4,1,2,5,6,3]$$$: The only cycle is $$$(1\,4\,5\,6\,3\,2)$$$, with length $$$6$$$.
- $$$[4,6,2,5,1,3]$$$: The cycles are $$$(1\,4\,5)$$$ and $$$(2\,6\,3)$$$, with lengths $$$3$$$ and $$$3$$$.
- $$$[4,6,2,5,3,1]$$$: The only cycle is $$$(1\,4\,5\,3\,2\,6)$$$, with length $$$6$$$.

In the second sample, the first update creates a cycle of length $$$1$$$, so there are no ways to make all cycle lengths a multiple of $$$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.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 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
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 python3.

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

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

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
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 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.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.