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

# Problem
A brick is a strip of size $$$1 \times k$$$, placed horizontally or vertically, where $$$k$$$ can be an arbitrary number that is at least $$$2$$$ ($$$k \ge 2$$$).

A brick wall of size $$$n \times m$$$ is such a way to place several bricks inside a rectangle $$$n \times m$$$, that all bricks lie either horizontally or vertically in the cells, do not cross the border of the rectangle, and that each cell of the $$$n \times m$$$ rectangle belongs to exactly one brick. Here $$$n$$$ is the height of the rectangle $$$n \times m$$$ and $$$m$$$ is the width. Note that there can be bricks with different values of k in the same brick wall.

The wall stability is the difference between the number of horizontal bricks and the number of vertical bricks. Note that if you used $$$0$$$ horizontal bricks and $$$2$$$ vertical ones, then the stability will be $$$-2$$$, not $$$2$$$.

What is the maximal possible stability of a wall of size $$$n \times m$$$?

It is guaranteed that under restrictions in the statement at least one $$$n \times m$$$ wall exists.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10\,000$$$), the number of test cases.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n,\,m \le 10^4$$$).

## Output Format
For each test case, print one integer, the maximum stability of a wall of size $$$n \times m$$$.

## Examples
```input
5
2 2
7 8
16 9
3 5
10000 10000
```
```output
2
28
64
6
50000000
```

## Note
In the 1st test case, the maximum stability of $$$2$$$ is obtained by placing two horizontal bricks $$$1 \times 2$$$ one on top of the other.

In the 2nd test case, one can get the maximum stability of $$$28$$$ by placing $$$4$$$ horizontal bricks $$$1 \times 2$$$ in each of the $$$7$$$ rows.

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
You are given two permutations $$$a$$$ and $$$b$$$ of length $$$n$$$. A permutation is an array of $$$n$$$ elements from $$$1$$$ to $$$n$$$ where all elements are distinct. For example, an array [$$$2,1,3$$$] is a permutation, but [$$$0,1$$$] and [$$$1,3,1$$$] aren't.

You can (as many times as you want) choose two indices $$$i$$$ and $$$j$$$, then swap $$$a_i$$$ with $$$a_j$$$ and $$$b_i$$$ with $$$b_j$$$ simultaneously.

You hate inversions, so you want to minimize the total number of inversions in both permutations.

An inversion in a permutation $$$p$$$ is a pair of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$p_i > p_j$$$. For example, if $$$p=[3,1,4,2,5]$$$ then there are $$$3$$$ inversions in it (the pairs of indices are $$$(1,2)$$$, $$$(1,4)$$$ and $$$(3,4)$$$).

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 20\,000$$$) — the number of test cases.

Each test case consists of three lines. The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the permutations $$$a$$$ and $$$b$$$. The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — permutation $$$a$$$. The third line contains $$$b$$$ in a similar format.

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

## Output Format
For each test case, output two permutations $$$a'$$$ and $$$b'$$$ (in the same format as in the input) — the permutations after all operations. The total number of inversions in $$$a'$$$ and $$$b'$$$ should be the minimum possible among all pairs of permutations that can be obtained using operations from the statement.

If there are multiple solutions, print any of them.

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

## Note
In the first test case, the minimum possible number of inversions is $$$10$$$.

In the second test case, we can sort both permutations at the same time. For this, the following operations can be done:

- Swap the elements in the positions $$$1$$$ and $$$3$$$ in both permutations. After the operation, $$$a =$$$ [$$$2,1,3$$$], $$$b =$$$ [$$$2,1,3$$$].
- Swap the elements in the positions $$$1$$$ and $$$2$$$. After the operations, $$$a$$$ and $$$b$$$ are sorted.

In the third test case, the minimum possible number of inversions is $$$7$$$.

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
You are given integers $$$a$$$, $$$b$$$, $$$r$$$. Find the smallest value of $$$|({a \oplus x}) - ({b \oplus x})|$$$ among all $$$0 \leq x \leq r$$$.

$$$\oplus$$$ is the operation of bitwise XOR, and $$$|y|$$$ is absolute value of $$$y$$$.

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

Each test case contains integers $$$a$$$, $$$b$$$, $$$r$$$ ($$$0 \le a, b, r \le 10^{18}$$$).

## Output Format
For each test case, output a single number — the smallest possible value.

## Examples
```input
10
4 6 0
0 3 2
9 6 10
92 256 23
165 839 201
1 14 5
2 7 2
96549 34359 13851
853686404475946 283666553522252166 127929199446003072
735268590557942972 916721749674600979 895150420120690183
```
```output
2
1
1
164
542
5
3
37102
27934920819538516
104449824168870225
```

## Note
In the first test, when $$$r = 0$$$, then $$$x$$$ is definitely equal to $$$0$$$, so the answer is $$$|{4 \oplus 0} - {6 \oplus 0}| = |4 - 6| = 2$$$.

In the second test:

- When $$$x = 0$$$, $$$|{0 \oplus 0} - {3 \oplus 0}| = |0 - 3| = 3$$$.
- When $$$x = 1$$$, $$$|{0 \oplus 1} - {3 \oplus 1}| = |1 - 2| = 1$$$.
- When $$$x = 2$$$, $$$|{0 \oplus 2} - {3 \oplus 2}| = |2 - 1| = 1$$$.

Therefore, the answer is $$$1$$$.

In the third test, the minimum is achieved when $$$x = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The caterpillar decided to visit every node of the tree. Initially, it is sitting at the root.

The tree is represented as a rooted tree with the root at the node $$$1$$$. Each crawl to a neighboring node takes $$$1$$$ minute for the caterpillar.

And there is a trampoline under the tree. If the caterpillar detaches from the tree and falls onto the trampoline, it will end up at the root of the tree in $$$0$$$ seconds. But the trampoline is old and can withstand no more than $$$k$$$ caterpillar's falls.

What is the minimum time the caterpillar can take to visit all the nodes of the tree?

More formally, we need to find the minimum time required to visit all the nodes of the tree, if the caterpillar starts at the root (node $$$1$$$) and moves using two methods.

1. Crawl along an edge to one of the neighboring nodes: takes $$$1$$$ minute.
2. Teleport to the root: takes no time,  no new nodes become visited.

The second method (teleportation) can be used at most $$$k$$$ times. The caterpillar can finish the journey at any node.

## Input Format
The first line of the input contains two integers: $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$) — the number of nodes in the tree, and $$$k$$$ ($$$0 \le k \le 10^9$$$) — the maximum number of teleports to the root.

The second line contains $$$n-1$$$ integers $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$ ($$$1 \le p_i \le n$$$) — the ancestors in the tree for nodes $$$2, 3, \ldots, n$$$; node $$$1$$$ is the root.

## Output Format
Print a single number in a single line — the minimum number of minutes required to visit all the nodes of the tree.

## Examples
```input
8 1
1 1 2 2 4 3 3
```
```output
9
```
-----
```input
4 0
4 4 1
```
```output
4
```

## Note
The figure shows one of the ways to traverse the tree from the first test in 9 minutes.

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 were given only one number, $$$n$$$. It didn't seem interesting to you, so you wondered if it's possible to come up with an array of length $$$n$$$ consisting of non-zero integers, such that if each element of the array is replaced by the sum of its neighbors (the elements on the ends are replaced by their only neighbors), you obtain a permutation of the numbers in the original array.

## Input Format
Each test case contains only one number, $$$n$$$ ($$$2 \leq n \leq 10^6$$$).

## Output Format
If a solution exists, output "YES" (without quotes), followed by an array $$$a$$$ ($$$-10^9 \leq a_i \leq 10^9, a_i \neq 0$$$) that satisfies the condition of the problem. If there are multiple possible answers, output any of them.

If there is no suitable array, output "NO" (without quotes).

The words "YES" and "NO" can be output in any case, for example, "YES", "Yes", "yEs", and so on.

## Examples
```input
4
```
```output
YES
1 2 -2 -1
```
-----
```input
5
```
```output
NO
```

## Note
In the first test, the array [$$$1, 2, -2, -1$$$] is suitable, because if each element is replaced by the sum of its neighbors, the resulting array is [$$$2, -1, 1, -2$$$], which is a permutation of the original array.

In the second test, it can be shown that there is no solution.

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
Sasha decided to give his girlfriend an array $$$a_1, a_2, \ldots, a_n$$$. He found out that his girlfriend evaluates the beauty of the array as the sum of the values $$$(a_i - a_{i - 1})$$$ for all integers $$$i$$$ from $$$2$$$ to $$$n$$$.

Help Sasha and tell him the maximum beauty of the array $$$a$$$ that he can obtain, if he can rearrange its elements in any way.

## 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 \leq n \leq 100$$$) — the length of the array $$$a$$$.

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

## Output Format
For each test case, output a single integer — the maximum beauty of the array $$$a$$$ that can be obtained.

## Examples
```input
5
3
2 1 3
3
69 69 69
5
100 54 80 43 90
4
3 4 3 3
2
2 1
```
```output
2
0
57
1
1
```

## Note
In the first test case, the elements of the array $$$a$$$ can be rearranged to make $$$a = [1, 2, 3]$$$. Then its beauty will be equal to $$$(a_2 - a_1) + (a_3 - a_2) = (2 - 1) + (3 - 2) = 2$$$.

In the second test case, there is no need to rearrange the elements of the array $$$a$$$. Then its beauty will be equal to $$$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
Even in kindergarten, Sasha liked a girl. Therefore, he wanted to give her a drawing and attract her attention.

As a drawing, he decided to draw a square grid of size $$$n \times n$$$, in which some cells are colored. But coloring the cells is difficult, so he wants to color as few cells as possible. But at the same time, he wants at least $$$k$$$ diagonals to have at least one colored cell. Note that the square grid of size $$$n \times n$$$ has a total of $$$4n - 2$$$ diagonals.

Help little Sasha to make the girl fall in love with him and tell him the minimum number of cells he needs to color.

## 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 test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^8$$$, $$$1 \leq k \leq 4n - 2$$$) — the size of the square grid and the minimum number of diagonals in which there should be at least one colored cell.

## Output Format
For each test case, output a single integer — the minimum number of cells that need to be colored.

## Examples
```input
7
3 4
3 3
3 10
3 9
4 7
7 11
2 3
```
```output
2
2
6
5
4
6
2
```

## Note
In the pictures below, the colored cells are marked in black, and all diagonals are marked in purple.

In the first test case, you can color $$$2$$$ cells so that $$$4$$$ diagonals contain at least one colored cell:

In the third test case, you can color $$$6$$$ cells so that all $$$10$$$ diagonals contain at least one colored cell:

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
Sasha was given a tree$$$^{\dagger}$$$ with $$$n$$$ vertices as a prize for winning yet another competition. However, upon returning home after celebrating his victory, he noticed that some parts of the tree were missing. Sasha remembers that he colored some of the edges of this tree. He is certain that for any of the $$$k$$$ pairs of vertices $$$(a_1, b_1), \ldots, (a_k, b_k)$$$, he colored at least one edge on the simple path$$$^{\ddagger}$$$ between vertices $$$a_i$$$ and $$$b_i$$$.

Sasha does not remember how many edges he exactly colored, so he asks you to tell him the minimum number of edges he could have colored to satisfy the above condition.

$$$^{\dagger}$$$A tree is an undirected connected graph without cycles.

$$$^{\ddagger}$$$A simple path is a path that passes through each vertex at most once.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 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 10^5$$$) — the number of vertices in the tree.

The next $$$(n - 1)$$$ lines describe the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — the numbers of the vertices connected by the $$$i$$$-th edge.

The next line contains a single integer $$$k$$$ ($$$1 \leq k \leq 20$$$) — the number of pairs of vertices between which Sasha colored at least one edge on a simple path.

The next $$$k$$$ lines describe pairs. The $$$j$$$-th line contains two integers $$$a_j$$$ and $$$b_j$$$ ($$$1 \leq a_j, b_j \leq n, a_j \neq b_j$$$) — the vertices in the $$$j$$$-th pair.

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

## Output Format
For each test case, output a single integer — the minimum number of edges Sasha could have colored.

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

## Note
In the first test case, Sasha could have colored only one edge $$$(1, 2)$$$. Then, there would be at least one colored edge on the simple path between vertices $$$1$$$ and $$$3$$$, and vertices $$$4$$$ and $$$1$$$.

In the second test case, Sasha could have colored the edges $$$(1, 6)$$$ and $$$(1, 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
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.