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
You are given a tree with $$$n$$$ vertices, whose vertices are numbered from $$$1$$$ to $$$n$$$. Each edge is labeled with some integer $$$w_i$$$.

Define $$$len(u, v)$$$ as the number of edges in the simple path between vertices $$$u$$$ and $$$v$$$, and $$$gcd(u, v)$$$ as the Greatest Common Divisor of all numbers written on the edges of the simple path between vertices $$$u$$$ and $$$v$$$. For example, $$$len(u, u) = 0$$$ and $$$gcd(u, u) = 0$$$ for any $$$1 \leq u \leq n$$$.

You need to find the maximum value of $$$len(u, v) \cdot gcd(u, v)$$$ over all pairs of vertices in the tree.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. This is followed by their description.

The first line of each test case contains the number $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices in the tree.

The next $$$n-1$$$ lines specify the edges in the format $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$1 \leq w \leq 10^{12}$$$).

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

## Output Format
For each test case, output a single number equal to the maximum value of $$$len(u, v) \cdot gcd(u, v)$$$ over all pairs of vertices in the tree.

## Examples
```input
4
2
1 2 1000000000000
4
3 2 6
2 1 10
2 4 6
8
1 2 12
2 3 9
3 4 9
4 5 6
5 6 12
6 7 4
7 8 9
12
1 2 12
2 3 12
2 4 6
2 5 9
5 6 6
1 7 4
4 8 12
8 9 4
8 10 12
2 11 9
7 12 9
```
```output
1000000000000
12
18
24
```

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
This is the easy version of the problem. The only differences between the two versions of this problem are the constraints on $$$k$$$. You can make hacks only if all versions of the problem are solved.

You are given integers $$$n$$$, $$$p$$$ and $$$k$$$. $$$p$$$ is guaranteed to be a prime number.

For each $$$r$$$ from $$$0$$$ to $$$k$$$, find the number of $$$n \times n$$$ matrices $$$A$$$ of the field$$$^\dagger$$$ of integers modulo $$$p$$$ such that the rank$$$^\ddagger$$$ of $$$A$$$ is exactly $$$r$$$. Since these values are big, you are only required to output them modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ https://en.wikipedia.org/wiki/Field_(mathematics)

$$$^\ddagger$$$ https://en.wikipedia.org/wiki/Rank_(linear_algebra)

## Input Format
The first line of input contains three integers $$$n$$$, $$$p$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$2 \leq p < 998\,244\,353$$$, $$$0 \leq k \leq 5000$$$).

It is guaranteed that $$$p$$$ is a prime number.

## Output Format
Output $$$k+1$$$ integers, the answers for each $$$r$$$ from $$$0$$$ to $$$k$$$.

## Examples
```input
3 2 3
```
```output
1 49 294 168
```
-----
```input
1 51549919 2
```
```output
1 51549918 0
```

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
This is the hard version of the problem. The only differences between the two versions of this problem are the constraints on $$$k$$$. You can make hacks only if all versions of the problem are solved.

You are given integers $$$n$$$, $$$p$$$ and $$$k$$$. $$$p$$$ is guaranteed to be a prime number.

For each $$$r$$$ from $$$0$$$ to $$$k$$$, find the number of $$$n \times n$$$ matrices $$$A$$$ of the field$$$^\dagger$$$ of integers modulo $$$p$$$ such that the rank$$$^\ddagger$$$ of $$$A$$$ is exactly $$$r$$$. Since these values are big, you are only required to output them modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ https://en.wikipedia.org/wiki/Field_(mathematics)

$$$^\ddagger$$$ https://en.wikipedia.org/wiki/Rank_(linear_algebra)

## Input Format
The first line of input contains three integers $$$n$$$, $$$p$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$2 \leq p < 998\,244\,353$$$, $$$0 \leq k \leq 5 \cdot 10^5$$$).

It is guaranteed that $$$p$$$ is a prime number.

## Output Format
Output $$$k+1$$$ integers, the answers for each $$$r$$$ from $$$0$$$ to $$$k$$$.

## Examples
```input
3 2 3
```
```output
1 49 294 168
```
-----
```input
1 51549919 2
```
```output
1 51549918 0
```

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
Polycarp lost the string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters, but he still has its trace.

The trace of the string $$$s$$$ is an array $$$a$$$ of $$$n$$$ integers, where $$$a_i$$$ is the number of such indices $$$j$$$ ($$$j < i$$$) that $$$s_i=s_j$$$. For example, the trace of the string abracadabra is the array [$$$0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4$$$].

Given a trace of a string, find any string $$$s$$$ from which it could have been obtained. The string $$$s$$$ should consist only of lowercase Latin letters a-z.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the lost string.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < n$$$) — the trace of the string. It is guaranteed that for the given trace, there exists a suitable string $$$s$$$.

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 a string $$$s$$$ that corresponds to the given trace. If there are multiple such strings $$$s$$$, then output any of them.

The string $$$s$$$ should consist of lowercase Latin letters a-z.

It is guaranteed that for each test case, a valid answer exists.

## Examples
```input
5
11
0 0 0 1 0 2 0 3 1 1 4
10
0 0 0 0 0 1 0 1 1 0
1
0
8
0 1 2 3 4 5 6 7
8
0 0 0 0 0 0 0 0
```
```output
abracadabra
codeforces
a
aaaaaaaa
dijkstra
```

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 two integers $$$n$$$ and $$$k$$$ ($$$k \le n$$$), where $$$k$$$ is even.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation (as $$$2$$$ appears twice in the array) and $$$[0,1,2]$$$ is also not a permutation (as $$$n=3$$$, but $$$3$$$ is not present in the array).

Your task is to construct a $$$k$$$-level permutation of length $$$n$$$.

A permutation is called $$$k$$$-level if, among all the sums of continuous segments of length $$$k$$$ (of which there are exactly $$$n - k + 1$$$), any two sums differ by no more than $$$1$$$.

More formally, to determine if the permutation $$$p$$$ is $$$k$$$-level, first construct an array $$$s$$$ of length $$$n - k + 1$$$, where $$$s_i=\sum_{j=i}^{i+k-1} p_j$$$, i.e., the $$$i$$$-th element is equal to the sum of $$$p_i, p_{i+1}, \dots, p_{i+k-1}$$$.

A permutation is called $$$k$$$-level if $$$\max(s) - \min(s) \le 1$$$.

Find any $$$k$$$-level permutation of length $$$n$$$.

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. This is followed by the description of the test cases.

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$, $$$k$$$ is even), where $$$n$$$ is the length of the desired permutation.

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

## Output Format
For each test case, output any $$$k$$$-level permutation of length $$$n$$$.

It is guaranteed that such a permutation always exists given the constraints.

## Examples
```input
5
2 2
3 2
10 4
13 4
7 4
```
```output
2 1
1 3 2
1 8 4 10 2 7 5 9 3 6
4 10 1 13 5 9 2 12 6 8 3 11 7
1 6 3 7 2 5 4
```

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

- $$$p_1 + p_2 = 3 + 1 = 4$$$;
- $$$p_2 + p_3 = 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 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Given an undirected weighted graph with $$$n$$$ vertices and $$$m$$$ edges. There is at most one edge between each pair of vertices in the graph, and the graph does not contain loops (edges from a vertex to itself). The graph is not necessarily connected.

A cycle in the graph is called simple if it doesn't pass through the same vertex twice and doesn't contain the same edge twice.

Find any simple cycle in this graph in which the weight of the lightest edge is minimal.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$$$) — the size of the graph and the number of edges.

The next $$$m$$$ lines of the test case contain three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$1 \le w \le 10^6$$$) — vertices $$$u$$$ and $$$v$$$ are connected by an edge of weight $$$w$$$.

It is guaranteed that there is at most one edge between each pair of vertices. Note that under the given constraints, there is always at least one simple cycle in the graph.

It is guaranteed that the sum of the values of $$$m$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a pair of numbers $$$b$$$ and $$$k$$$, where:

- $$$b$$$ — the minimum weight of the edge in the found cycle,
- $$$k$$$ — the number of vertices in the found cycle.

On the next line, output $$$k$$$ numbers from $$$1$$$ to $$$n$$$  — the vertices of the cycle in traversal order.

Note that the answer always exists, as under the given constraints, there is always at least one simple cycle in the graph.

## Examples
```input
5
6 6
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
6 6
1 2 10
2 3 8
3 1 5
4 5 100
5 6 40
6 4 3
6 15
1 2 4
5 2 8
6 1 7
6 3 10
6 5 1
3 2 8
4 3 4
5 3 6
2 6 6
5 4 5
4 1 3
6 4 5
4 2 1
3 1 7
1 5 5
4 6
2 3 2
1 3 10
1 4 1
3 4 7
2 4 5
1 2 2
4 5
2 1 10
3 1 3
4 2 6
1 4 7
2 3 3
```
```output
1 3
1 2 3 
3 3
6 4 5 
1 5
4 2 1 6 3 
1 4
1 4 3 2 
3 3
2 3 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
A horizontal grid strip of $$$n$$$ cells is given. In the $$$i$$$-th cell, there is a paint charge of size $$$a_i$$$. This charge can be:

- either used to the left — then all cells to the left at a distance less than $$$a_i$$$ (from $$$\max(i - a_i + 1, 1)$$$ to $$$i$$$ inclusive) will be painted,
- or used to the right — then all cells to the right at a distance less than $$$a_i$$$ (from $$$i$$$ to $$$\min(i + a_i - 1, n)$$$ inclusive) will be painted,
- or not used at all.

Note that a charge can be used no more than once (that is, it cannot be used simultaneously to the left and to the right). It is allowed for a cell to be painted more than once.

What is the minimum number of times a charge needs to be used to paint all the cells of the strip?

## Input Format
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases in the test. This is followed by descriptions of $$$t$$$ test cases.

Each test case is specified by two lines. The first one contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of cells in the strip. The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the size of the paint charge in the $$$i$$$-th cell from the left of the strip.

It is guaranteed that the sum of the values of $$$n$$$ in the test does not exceed $$$1000$$$.

## Output Format
For each test case, output the minimum number of times the charges need to be used to paint all the cells of the strip.

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

## Note
In the third test case of the example, it is sufficient to use the charge from the $$$1$$$-st cell to the right, then it will cover both cells $$$1$$$ and $$$2$$$.

In the ninth test case of the example, you need to:

- use the charge from the $$$3$$$-rd cell to the left, covering cells from the $$$1$$$-st to the $$$3$$$-rd;
- use the charge from the $$$5$$$-th cell to the left, covering cells from the $$$4$$$-th to the $$$5$$$-th;
- use the charge from the $$$7$$$-th cell to the left, covering cells from the $$$6$$$-th to the $$$7$$$-th.

In the eleventh test case of the example, you need to:

- use the charge from the $$$5$$$-th cell to the right, covering cells from the $$$5$$$-th to the $$$10$$$-th;
- use the charge from the $$$7$$$-th cell to the left, covering cells from the $$$1$$$-st to the $$$7$$$-th.

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
There are $$$n$$$ containers of water lined up, numbered from left to right from $$$1$$$ to $$$n$$$. Each container can hold any amount of water; initially, the $$$i$$$-th container contains $$$a_i$$$ units of water. The sum of $$$a_i$$$ is divisible by $$$n$$$.

You can apply the following operation any (possibly zero) number of times: pour any amount of water from the $$$i$$$-th container to the $$$j$$$-th container, where $$$i$$$ must be less than $$$j$$$ (i.e. $$$i<j$$$). Any index can be chosen as $$$i$$$ or $$$j$$$ any number of times.

Determine whether it is possible to make the amount of water in all containers the same using this operation.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of containers with water.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the amounts of water in the containers. It is guaranteed that the sum of $$$a_i$$$ in each test case does not exceed $$$2 \cdot 10^9$$$. Also, the sum of $$$a_i$$$ is divisible by $$$n$$$.

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

## Output Format
Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As the answer, output "YES" if it is possible to make the amount of water in all containers the same using the described operation. Otherwise, output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

## Examples
```input
6
1
43
2
1 3
5
4 5 2 1 3
3
1 2 3
7
4 5 5 0 6 4 4
7
6 5 5 1 3 4 4
```
```output
YES
NO
YES
NO
NO
YES
```

## Note
In the third test case of the example ($$$a=[4, 5, 2, 1, 3]$$$), you can proceed as follows:

- pour $$$1$$$ unit of water from the first vessel to the fourth, then $$$a=[3, 5, 2, 2, 3]$$$;
- pour $$$1$$$ unit of water from the second vessel to the third, then $$$a=[3, 4, 3, 2, 3]$$$;
- pour $$$1$$$ unit of water from the second vessel to the fourth, then $$$a=[3, 3, 3, 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 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
Polycarp has two favorite integers $$$x$$$ and $$$y$$$ (they can be equal), and he has found an array $$$a$$$ of length $$$n$$$.

Polycarp considers a pair of indices $$$\langle i, j \rangle$$$ ($$$1 \le i < j \le n$$$) beautiful if:

- $$$a_i + a_j$$$ is divisible by $$$x$$$;
- $$$a_i - a_j$$$ is divisible by $$$y$$$.

For example, if $$$x=5$$$, $$$y=2$$$, $$$n=6$$$, $$$a=$$$[$$$1, 2, 7, 4, 9, 6$$$], then the only beautiful pairs are:

- $$$\langle 1, 5 \rangle$$$: $$$a_1 + a_5 = 1 + 9 = 10$$$ ($$$10$$$ is divisible by $$$5$$$) and $$$a_1 - a_5 = 1 - 9 = -8$$$ ($$$-8$$$ is divisible by $$$2$$$);
- $$$\langle 4, 6 \rangle$$$: $$$a_4 + a_6 = 4 + 6 = 10$$$ ($$$10$$$ is divisible by $$$5$$$) and $$$a_4 - a_6 = 4 - 6 = -2$$$ ($$$-2$$$ is divisible by $$$2$$$).

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

The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le x, y \le 10^9$$$) — the size of the array and Polycarp's favorite integers.

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

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 a single integer — the number of beautiful pairs in the array $$$a$$$.

## Examples
```input
7
6 5 2
1 2 7 4 9 6
7 9 5
1 10 15 3 8 12 15
9 4 10
14 10 2 2 11 11 13 5 6
9 5 6
10 7 6 7 9 7 7 10 10
9 6 2
4 9 7 1 2 2 13 3 15
9 2 3
14 6 1 15 12 15 8 2 15
10 5 7
13 3 3 2 12 11 3 7 13 14
```
```output
2
0
1
3
5
7
0
```

Now solve the problem and return the code.