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
Phoenix loves beautiful arrays. An array is beautiful if all its subarrays of length $$$k$$$ have the same sum. A subarray of an array is any sequence of consecutive elements.

Phoenix currently has an array $$$a$$$ of length $$$n$$$. He wants to insert some number of integers, possibly zero, into his array such that it becomes beautiful. The inserted integers must be between $$$1$$$ and $$$n$$$ inclusive. Integers may be inserted anywhere (even before the first or after the last element), and he is not trying to minimize the number of inserted integers.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$).

The second line of each test case contains $$$n$$$ space-separated integers ($$$1 \le a_i \le n$$$) — the array that Phoenix currently has. This array may or may not be already beautiful.

## Output Format
For each test case, if it is impossible to create a beautiful array, print -1. Otherwise, print two lines.

The first line should contain the length of the beautiful array $$$m$$$ ($$$n \le m \le 10^4$$$). You don't need to minimize $$$m$$$.

The second line should contain $$$m$$$ space-separated integers ($$$1 \le b_i \le n$$$) — a beautiful array that Phoenix can obtain after inserting some, possibly zero, integers into his array $$$a$$$. You may print integers that weren't originally in array $$$a$$$.

If there are multiple solutions, print any. It's guaranteed that if we can make array $$$a$$$ beautiful, we can always make it with resulting length no more than $$$10^4$$$.

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

## Note
In the first test case, we can make array $$$a$$$ beautiful by inserting the integer $$$1$$$ at index $$$3$$$ (in between the two existing $$$2$$$s). Now, all subarrays of length $$$k=2$$$ have the same sum $$$3$$$. There exists many other possible solutions, for example:

- $$$2, 1, 2, 1, 2, 1$$$
- $$$1, 2, 1, 2, 1, 2$$$

In the second test case, the array is already beautiful: all subarrays of length $$$k=3$$$ have the same sum $$$5$$$.

In the third test case, it can be shown that we cannot insert numbers to make array $$$a$$$ beautiful.

In the fourth test case, the array $$$b$$$ shown is beautiful and all subarrays of length $$$k=4$$$ have the same sum $$$10$$$. There exist other solutions also.

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
Phoenix is picking berries in his backyard. There are $$$n$$$ shrubs, and each shrub has $$$a_i$$$ red berries and $$$b_i$$$ blue berries.

Each basket can contain $$$k$$$ berries. But, Phoenix has decided that each basket may only contain berries from the same shrub or berries of the same color (red or blue). In other words, all berries in a basket must be from the same shrub or/and have the same color.

For example, if there are two shrubs with $$$5$$$ red and $$$2$$$ blue berries in the first shrub and $$$2$$$ red and $$$1$$$ blue berries in the second shrub then Phoenix can fill $$$2$$$ baskets of capacity $$$4$$$ completely:

- the first basket will contain $$$3$$$ red and $$$1$$$ blue berries from the first shrub;
- the second basket will contain the $$$2$$$ remaining red berries from the first shrub and $$$2$$$ red berries from the second shrub.

Help Phoenix determine the maximum number of baskets he can fill completely!

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$ 1\le n, k \le 500$$$) — the number of shrubs and the basket capacity, respectively.

The $$$i$$$-th of the next $$$n$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$) — the number of red and blue berries in the $$$i$$$-th shrub, respectively.

## Output Format
Output one integer — the maximum number of baskets that Phoenix can fill completely.

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

## Note
The first example is described above.

In the second example, Phoenix can fill one basket fully using all the berries from the first (and only) shrub.

In the third example, Phoenix cannot fill any basket completely because there are less than $$$5$$$ berries in each shrub, less than $$$5$$$ total red berries, and less than $$$5$$$ total blue berries.

In the fourth example, Phoenix can put all the red berries into baskets, leaving an extra blue berry behind.

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
Phoenix is trying to take a photo of his $$$n$$$ friends with labels $$$1, 2, \dots, n$$$ who are lined up in a row in a special order. But before he can take the photo, his friends get distracted by a duck and mess up their order.

Now, Phoenix must restore the order but he doesn't remember completely! He only remembers that the $$$i$$$-th friend from the left had a label between $$$a_i$$$ and $$$b_i$$$ inclusive. Does there exist a unique way to order his friends based of his memory?

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$)  — the number of friends.

The $$$i$$$-th of the next $$$n$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le b_i \le n$$$)  — Phoenix's memory of the $$$i$$$-th position from the left.

It is guaranteed that Phoenix's memory is valid so there is at least one valid ordering.

## Output Format
If Phoenix can reorder his friends in a unique order, print YES followed by $$$n$$$ integers  — the $$$i$$$-th integer should be the label of the $$$i$$$-th friend from the left.

Otherwise, print NO. Then, print any two distinct valid orderings on the following two lines. If are multiple solutions, print any.

## Examples
```input
4
4 4
1 3
2 4
3 4
```
```output
YES
4 1 2 3
```
-----
```input
4
1 3
2 4
3 4
2 3
```
```output
NO
1 3 4 2 
1 2 4 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
Little Petya very much likes gifts. Recently he has received a new laptop as a New Year gift from his mother. He immediately decided to give it to somebody else as what can be more pleasant than giving somebody gifts. And on this occasion he organized a New Year party at his place and invited n his friends there.

If there's one thing Petya likes more that receiving gifts, that's watching others giving gifts to somebody else. Thus, he safely hid the laptop until the next New Year and made up his mind to watch his friends exchanging gifts while he does not participate in the process. He numbered all his friends with integers from 1 to n. Petya remembered that a friend number i gave a gift to a friend number pi. He also remembered that each of his friends received exactly one gift.

Now Petya wants to know for each friend i the number of a friend who has given him a gift.

## Input Format
The first line contains one integer n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party. The second line contains n space-separated integers: the i-th number is pi — the number of a friend who gave a gift to friend number i. It is guaranteed that each friend received exactly one gift. It is possible that some friends do not share Petya's ideas of giving gifts to somebody else. Those friends gave the gifts to themselves.

## Output Format
Print n space-separated integers: the i-th number should equal the number of the friend who gave a gift to friend number i.

## Examples
```input
4
2 3 4 1
```
```output
4 1 2 3
```
-----
```input
3
1 3 2
```
```output
1 3 2
```
-----
```input
2
1 2
```
```output
1 2
```

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
Little Petya very much likes computers. Recently he has received a new "Ternatron IV" as a gift from his mother. Unlike other modern computers, "Ternatron IV" operates with ternary and not binary logic. Petya immediately wondered how the xor operation is performed on this computer (and whether there is anything like it).

It turned out that the operation does exist (however, it is called tor) and it works like this. Suppose that we need to calculate the value of the expression a tor b. Both numbers a and b are written in the ternary notation one under the other one (b under a). If they have a different number of digits, then leading zeroes are added to the shorter number until the lengths are the same. Then the numbers are summed together digit by digit. The result of summing each two digits is calculated modulo 3. Note that there is no carry between digits (i. e. during this operation the digits aren't transferred). For example: 1410 tor 5010 = 01123 tor 12123 = 10213 = 3410.

Petya wrote numbers a and c on a piece of paper. Help him find such number b, that a tor b = c. If there are several such numbers, print the smallest one.

## Input Format
The first line contains two integers a and c (0 ≤ a, c ≤ 109). Both numbers are written in decimal notation.

## Output Format
Print the single integer b, such that a tor b = c. If there are several possible numbers b, print the smallest one. You should print the number in decimal notation.

## Examples
```input
14 34
```
```output
50
```
-----
```input
50 34
```
```output
14
```
-----
```input
387420489 225159023
```
```output
1000000001
```
-----
```input
5 5
```
```output
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 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$$$ of length $$$n$$$, which initially is a permutation of numbers from $$$1$$$ to $$$n$$$. In one operation, you can choose an index $$$i$$$ ($$$1 \leq i < n$$$) such that $$$a_i < a_{i + 1}$$$, and remove either $$$a_i$$$ or $$$a_{i + 1}$$$ from the array (after the removal, the remaining parts are concatenated).

For example, if you have the array $$$[1, 3, 2]$$$, you can choose $$$i = 1$$$ (since $$$a_1 = 1 < a_2 = 3$$$), then either remove $$$a_1$$$ which gives the new array $$$[3, 2]$$$, or remove $$$a_2$$$ which gives the new array $$$[1, 2]$$$.

Is it possible to make the length of this array equal to $$$1$$$ with these operations?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$)  — 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 \leq n \leq 3 \cdot 10^5$$$)  — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq n$$$, $$$a_i$$$ are pairwise distinct) — elements of the array.

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

## Output Format
For each test case, output on a single line the word "YES" if it is possible to reduce the array to a single element using the aforementioned operation, or "NO" if it is impossible to do so.

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

## Note
For the first two test cases and the fourth test case, we can operate as follow (the bolded elements are the pair chosen for that operation):

$$$[\text{1}, \textbf{2}, \textbf{3}] \rightarrow [\textbf{1}, \textbf{2}] \rightarrow [\text{1}]$$$

$$$[\text{3}, \textbf{1}, \textbf{2}, \text{4}] \rightarrow [\text{3}, \textbf{1}, \textbf{4}] \rightarrow [\textbf{3}, \textbf{4}] \rightarrow [\text{4}]$$$

$$$[\textbf{2}, \textbf{4}, \text{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\textbf{4}, \textbf{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\text{4}, \text{1}, \textbf{3}, \textbf{5}] \rightarrow [\text{4}, \textbf{1}, \textbf{5}] \rightarrow [\textbf{4}, \textbf{5}] \rightarrow [\text{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 tree with $$$n$$$ vertices. You are allowed to modify the structure of the tree through the following multi-step operation:

1. Choose three vertices $$$a$$$, $$$b$$$, and $$$c$$$ such that $$$b$$$ is adjacent to both $$$a$$$ and $$$c$$$.
2. For every vertex $$$d$$$ other than $$$b$$$ that is adjacent to $$$a$$$, remove the edge connecting $$$d$$$ and $$$a$$$ and add the edge connecting $$$d$$$ and $$$c$$$.
3. Delete the edge connecting $$$a$$$ and $$$b$$$ and add the edge connecting $$$a$$$ and $$$c$$$.

As an example, consider the following tree:

The following diagram illustrates the sequence of steps that happen when we apply an operation to vertices $$$2$$$, $$$4$$$, and $$$5$$$:

It can be proven that after each operation, the resulting graph is still a tree.

Find the minimum number of operations that must be performed to transform the tree into a star. A star is a tree with one vertex of degree $$$n - 1$$$, called its center, and $$$n - 1$$$ vertices of degree $$$1$$$.

## Input Format
The first line contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$)  — the number of vertices in the tree.

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) denoting that there exists an edge connecting vertices $$$u_i$$$ and $$$v_i$$$. It is guaranteed that the given edges form a tree.

## Output Format
Print a single integer  — the minimum number of operations needed to transform the tree into a star.

It can be proven that under the given constraints, it is always possible to transform the tree into a star using at most $$$10^{18}$$$ operations.

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

## Note
The first test case corresponds to the tree shown in the statement. As we have seen before, we can transform the tree into a star with center at vertex $$$5$$$ by applying a single operation to vertices $$$2$$$, $$$4$$$, and $$$5$$$.

In the second test case, the given tree is already a star with the center at vertex $$$4$$$, so no operations have to be performed.

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

# Problem
A cubic lattice $$$L$$$ in $$$3$$$-dimensional euclidean space is a set of points defined in the following way: $$$$$$L=\{u \cdot \vec r_1 + v \cdot \vec r_2 + w \cdot \vec r_3\}_{u, v, w \in \mathbb Z}$$$$$$ Where $$$\vec r_1, \vec r_2, \vec r_3 \in \mathbb{Z}^3$$$ are some integer vectors such that:

- $$$\vec r_1$$$, $$$\vec r_2$$$ and $$$\vec r_3$$$ are pairwise orthogonal: $$$$$$\vec r_1 \cdot \vec r_2 = \vec r_1 \cdot \vec r_3 = \vec r_2 \cdot \vec r_3 = 0$$$$$$ Where $$$\vec a \cdot \vec b$$$ is a dot product of vectors $$$\vec a$$$ and $$$\vec b$$$.
- $$$\vec r_1$$$, $$$\vec r_2$$$ and $$$\vec r_3$$$ all have the same length: $$$$$$|\vec r_1| = |\vec r_2| = |\vec r_3| = r$$$$$$

You have to find a cubic lattice $$$L$$$ such that $$$A \subset L$$$ and $$$r$$$ is the maximum possible.

## Input Format
First line contains single integer $$$n$$$ ($$$1 \leq n \leq 10^4$$$) — the number of points in $$$A$$$.

The $$$i$$$-th of the following $$$n$$$ lines contains integers $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ ($$$0 < x_i^2 + y_i^2 + z_i^2 \leq 10^{16}$$$) — coordinates of the $$$i$$$-th point.

It is guaranteed that $$$\gcd(g_1,g_2,\dots,g_n)=1$$$ where $$$g_i=\gcd(x_i,y_i,z_i)$$$.

## Output Format
In first line output a single integer $$$r^2$$$, the square of maximum possible $$$r$$$.

In following $$$3$$$ lines output coordinates of vectors $$$\vec r_1$$$, $$$\vec r_2$$$ and $$$\vec r_3$$$ respectively.

If there are multiple possible answers, output any.

## Examples
```input
2
1 2 3
1 2 1
```
```output
1
1 0 0
0 1 0
0 0 1
```
-----
```input
1
1 2 2
```
```output
9
2 -2 1
1 2 2
-2 -1 2
```
-----
```input
1
2 5 5
```
```output
9
-1 2 2
2 -1 2
2 2 -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: 1.0 seconds
Memory limit: 512.0 MB

# Problem
Vladimir would like to prepare a present for his wife: they have an anniversary! He decided to buy her exactly $$$n$$$ flowers.

Vladimir went to a flower shop, and he was amazed to see that there are $$$m$$$ types of flowers being sold there, and there is unlimited supply of flowers of each type. Vladimir wants to choose flowers to maximize the happiness of his wife. He knows that after receiving the first flower of the $$$i$$$-th type happiness of his wife increases by $$$a_i$$$ and after receiving each consecutive flower of this type her happiness increases by $$$b_i$$$. That is, if among the chosen flowers there are $$$x_i > 0$$$ flowers of type $$$i$$$, his wife gets $$$a_i + (x_i - 1) \cdot b_i$$$ additional happiness (and if there are no flowers of type $$$i$$$, she gets nothing for this particular type).

Please help Vladimir to choose exactly $$$n$$$ flowers to maximize the total happiness of his wife.

## Input Format
The first line contains the only integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$), the number of test cases. It is followed by $$$t$$$ descriptions of the test cases.

Each test case description starts with two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 100\,000$$$), the number of flowers Vladimir needs to choose and the number of types of available flowers.

The following $$$m$$$ lines describe the types of flowers: each line contains integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$) for $$$i$$$-th available type of flowers.

The test cases are separated by a blank line. It is guaranteed that the sum of values $$$m$$$ among all test cases does not exceed $$$100\,000$$$.

## Output Format
For each test case output a single integer: the maximum total happiness of Vladimir's wife after choosing exactly $$$n$$$ flowers optimally.

## Examples
```input
2
4 3
5 0
1 4
2 2

5 3
5 2
4 2
3 1
```
```output
14
16
```

## Note
In the first example case Vladimir can pick 1 flower of the first type and 3 flowers of the second type, in this case the total happiness equals $$$5 + (1 + 2 \cdot 4) = 14$$$.

In the second example Vladimir can pick 2 flowers of the first type, 2 flowers of the second type, and 1 flower of the third type, in this case the total happiness equals $$$(5 + 1 \cdot 2) + (4 + 1 \cdot 2) + 3 = 16$$$.

Now solve the problem and return the code.