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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Since Hayate didn't get any Christmas presents from Santa, he is instead left solving a tree query problem.

Hayate has a tree with $$$n$$$ nodes.

Hayate now wants you to answer $$$q$$$ queries. Each query consists of a node $$$x$$$ and $$$k$$$ other additional nodes $$$a_1,a_2,\ldots,a_k$$$. These $$$k+1$$$ nodes are guaranteed to be all distinct.

For each query, you must find the length of the longest simple path starting at node $$$x^\dagger$$$ after removing nodes $$$a_1,a_2,\ldots,a_k$$$ along with all edges connected to at least one of nodes $$$a_1,a_2,\ldots,a_k$$$.

$$$^\dagger$$$ A simple path of length $$$k$$$ starting at node $$$x$$$ is a sequence of distinct nodes $$$x=u_0,u_1,\ldots,u_k$$$ such that there exists a edge between nodes $$$u_{i-1}$$$ and $$$u_i$$$ for all $$$1 \leq i \leq k$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of nodes of the tree and the number of queries.

The following $$$n - 1$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — denoting an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

The following $$$q$$$ lines describe the queries. Each line contains the integers $$$x$$$, $$$k$$$ and $$$a_1,a_2,\ldots,a_k$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq k < n$$$, $$$1 \leq a_i \leq n$$$) — the starting node, the number of removed nodes and the removed nodes.

It is guaranteed that for each query, $$$x,a_1,a_2,\ldots,a_k$$$ are all distinct.

It is guaranteed that the sum of $$$k$$$ over all queries will not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each query, output a single integer denoting the answer for that query.

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

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

In the first query, no nodes are missing. The longest simple path starting from node $$$2$$$ is $$$2 \to 1 \to 3 \to 4$$$. Thus, the answer is $$$3$$$.

In the third query, nodes $$$1$$$ and $$$6$$$ are missing and the tree is shown below. The longest simple path starting from node $$$2$$$ is $$$2 \to 5$$$. Thus, the answer is $$$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: 512.0 MB

# Problem
Lunchbox has a tree of size $$$n$$$ rooted at node $$$1$$$. Each node is then assigned a value. Lunchbox considers the tree to be beautiful if each value is distinct and ranges from $$$1$$$ to $$$n$$$. In addition, a beautiful tree must also satisfy $$$m$$$ requirements of $$$2$$$ types:

- "1 a b c" — The node with the smallest value on the path between nodes $$$a$$$ and $$$b$$$ must be located at $$$c$$$.
- "2 a b c" — The node with the largest value on the path between nodes $$$a$$$ and $$$b$$$ must be located at $$$c$$$.

Now, you must assign values to each node such that the resulting tree is beautiful. If it is impossible to do so, output $$$-1$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$).

The next $$$n - 1$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$) — denoting an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

The next $$$m$$$ lines each contain four integers $$$t$$$, $$$a$$$, $$$b$$$, and $$$c$$$ ($$$t \in \{1,2\}$$$, $$$1 \le a, b, c \le n$$$). It is guaranteed that node $$$c$$$ is on the path between nodes $$$a$$$ and $$$b$$$.

## Output Format
If it is impossible to assign values such that the tree is beautiful, output $$$-1$$$. Otherwise, output $$$n$$$ integers, the $$$i$$$-th of which denotes the value of node $$$i$$$.

## Examples
```input
7 5
1 2
1 3
1 4
3 5
4 6
3 7
1 6 5 1
2 6 7 3
1 2 7 1
1 7 5 7
2 4 2 2
```
```output
1 6 7 5 3 4 2
```
-----
```input
2 2
1 2
1 1 2 1
1 1 2 2
```
```output
-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: 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 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 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 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 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 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 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 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: 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 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A square of positive (strictly greater than $$$0$$$) area is located on the coordinate plane, with sides parallel to the coordinate axes. You are given the coordinates of its corners, in random order. Your task is to find the area of the square.

## Input Format
Each test consists of several testcases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases. The following is a description of the testcases.

Each testcase contains four lines, each line contains two integers $$$x_i, y_i$$$ ($$$-1000\le x_i, y_i\le 1000$$$), coordinates of the corners of the square.

It is guaranteed that there is a square with sides parallel to the coordinate axes, with positive (strictly greater than $$$0$$$) area, with corners in given points.

## Output Format
For each test case, print a single integer, the area of the square.

## Examples
```input
3
1 2
4 5
1 5
4 2
-1 1
1 -1
1 1
-1 -1
45 11
45 39
17 11
17 39
```
```output
9
4
784
```

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
Petya has an array $$$a_i$$$ of $$$n$$$ integers. His brother Vasya became envious and decided to make his own array of $$$n$$$ integers.

To do this, he found $$$m$$$ integers $$$b_i$$$ ($$$m\ge n$$$), and now he wants to choose some $$$n$$$ integers of them and arrange them in a certain order to obtain an array $$$c_i$$$ of length $$$n$$$.

To avoid being similar to his brother, Vasya wants to make his array as different as possible from Petya's array. Specifically, he wants the total difference $$$D = \sum_{i=1}^{n} |a_i - c_i|$$$ to be as large as possible.

Help Vasya find the maximum difference $$$D$$$ he can obtain.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le m\le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1\le a_i\le 10^9$$$). The third line of each test case contains $$$m$$$ integers $$$b_i$$$ ($$$1\le b_i\le 10^9$$$).

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

## Output Format
For each test case, output a single integer — the maximum total difference $$$D$$$ that can be obtained.

## Examples
```input
9
4 6
6 1 2 4
3 5 1 7 2 3
3 4
1 1 1
1 1 1 1
5 5
1 2 3 4 5
1 2 3 4 5
2 6
5 8
8 7 5 8 2 10
2 2
4 1
9 6
4 6
8 10 6 4
3 10 6 1 8 9
3 5
6 5 2
1 7 9 7 2
5 5
9 10 6 3 7
5 9 2 3 9
1 6
3
2 7 10 1 1 5
```
```output
16
0
12
11
10
23
15
25
7
```

## Note
In the first example, Vasya can, for example, create the array $$$(1, 5, 7, 2)$$$. Then the total difference will be $$$D = |6-1|+|1-5|+|2-7|+|4-2| = 5+4+5+2 = 16$$$.

In the second example, all the integers available to Vasya are equal to 1, so he can only create the array $$$(1, 1, 1)$$$, for which the difference $$$D = 0$$$.

In the third example, Vasya can, for example, create the array $$$(5, 4, 3, 2, 1)$$$. Then the total difference will be $$$D = |1-5|+|2-4|+|3-3|+|4-2|+|5-1| = 4+2+0+2+4 = 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 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: 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.