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: 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 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 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 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: 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 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
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.