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
You are given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$.

You can perform the following operation any number of times (possibly zero): select an index $$$i$$$ ($$$1 \leq i \leq n$$$) and swap $$$a_i$$$ and $$$b_i$$$.

Let's define the cost of the array $$$a$$$ as $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2$$$. Similarly, the cost of the array $$$b$$$ is $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (b_i + b_j)^2$$$.

Your task is to minimize the total cost of two arrays.

## Input Format
Each test case consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 40$$$) — the number of test cases. The following is a description of the input data sets.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of both arrays.

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

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 100$$$) — elements of the second array.

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

## Output Format
For each test case, print the minimum possible total cost.

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

## Note
In the second test case, in one of the optimal answers after all operations $$$a = [2, 6, 4, 6]$$$, $$$b = [3, 7, 6, 1]$$$.

The cost of the array $$$a$$$ equals to $$$(2 + 6)^2 + (2 + 4)^2 + (2 + 6)^2 + (6 + 4)^2 + (6 + 6)^2 + (4 + 6)^2 = 508$$$.

The cost of the array $$$b$$$ equals to $$$(3 + 7)^2 + (3 + 6)^2 + (3 + 1)^2 + (7 + 6)^2 + (7 + 1)^2 + (6 + 1)^2 = 479$$$.

The total cost of two arrays equals to $$$508 + 479 = 987$$$.

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 an array $$$a$$$ of length $$$n$$$. Let $$$cnt_x$$$ be the number of elements from the array which are equal to $$$x$$$. Let's also define $$$f(x, y)$$$ as $$$(cnt_x + cnt_y) \cdot (x + y)$$$.

Also you are given $$$m$$$ bad pairs $$$(x_i, y_i)$$$. Note that if $$$(x, y)$$$ is a bad pair, then $$$(y, x)$$$ is also bad.

Your task is to find the maximum value of $$$f(u, v)$$$ over all pairs $$$(u, v)$$$, such that $$$u \neq v$$$, that this pair is not bad, and also that $$$u$$$ and $$$v$$$ each occur in the array $$$a$$$. It is guaranteed that such a pair exists.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$0 \le m \le 3 \cdot 10^5$$$) — the length of the array and the number of bad pairs.

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

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i < y_i \le 10^9$$$), which represent a bad pair. It is guaranteed that no bad pair occurs twice in the input. It is also guaranteed that $$$cnt_{x_i} > 0$$$ and $$$cnt_{y_i} > 0$$$.

It is guaranteed that for each test case there is a pair of integers $$$(u, v)$$$, $$$u \ne v$$$, that is not bad, and such that both of these numbers occur in $$$a$$$.

It is guaranteed that the total sum of $$$n$$$ and the total sum of $$$m$$$ don't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case print a single integer — the answer to the problem.

## Examples
```input
3
6 1
6 3 6 7 3 3
3 6
2 0
3 4
7 4
1 2 2 3 1 5 1
1 5
3 5
1 3
2 5
```
```output
40
14
15
```

## Note
In the first test case $$$3$$$, $$$6$$$, $$$7$$$ occur in the array.

- $$$f(3, 6) = (cnt_3 + cnt_6) \cdot (3 + 6) = (3 + 2) \cdot (3 + 6) = 45$$$. But $$$(3, 6)$$$ is bad so we ignore it.
- $$$f(3, 7) = (cnt_3 + cnt_7) \cdot (3 + 7) = (3 + 1) \cdot (3 + 7) = 40$$$.
- $$$f(6, 7) = (cnt_6 + cnt_7) \cdot (6 + 7) = (2 + 1) \cdot (6 + 7) = 39$$$.

The answer to the problem is $$$\max(40, 39) = 40$$$.

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 a tree with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The height of the $$$i$$$-th vertex is $$$h_i$$$. You can place any number of towers into vertices, for each tower you can choose which vertex to put it in, as well as choose its efficiency. Setting up a tower with efficiency $$$e$$$ costs $$$e$$$ coins, where $$$e > 0$$$.

It is considered that a vertex $$$x$$$ gets a signal if for some pair of towers at the vertices $$$u$$$ and $$$v$$$ ($$$u \neq v$$$, but it is allowed that $$$x = u$$$ or $$$x = v$$$) with efficiencies $$$e_u$$$ and $$$e_v$$$, respectively, it is satisfied that $$$\min(e_u, e_v) \geq h_x$$$ and $$$x$$$ lies on the path between $$$u$$$ and $$$v$$$.

Find the minimum number of coins required to set up towers so that you can get a signal at all vertices.

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$h_i$$$ ($$$1 \le h_i \le 10^9$$$) — the heights of the vertices.

Each of the next $$$n - 1$$$ lines contain a pair of numbers $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — an edge of the tree. It is guaranteed that the given edges form a tree.

## Output Format
Print one integer — the minimum required number of coins.

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

## Note
In the first test case it's optimal to install two towers with efficiencies $$$2$$$ at vertices $$$1$$$ and $$$3$$$.

In the second test case it's optimal to install a tower with efficiency $$$1$$$ at vertex $$$1$$$ and two towers with efficiencies $$$3$$$ at vertices $$$2$$$ and $$$5$$$.

In the third test case it's optimal to install two towers with efficiencies $$$6$$$ at vertices $$$1$$$ and $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vitaly gave Maxim $$$n$$$ numbers $$$1, 2, \ldots, n$$$ for his $$$16$$$-th birthday. Maxim was tired of playing board games during the celebration, so he decided to play with these numbers. In one step Maxim can choose two numbers $$$x$$$ and $$$y$$$ from the numbers he has, throw them away, and add two numbers $$$x + y$$$ and $$$|x - y|$$$ instead. He wants all his numbers to be equal after several steps and the sum of the numbers to be minimal.

Help Maxim to find a solution. Maxim's friends don't want to wait long, so the number of steps in the solution should not exceed $$$20n$$$. It is guaranteed that under the given constraints, if a solution exists, then there exists a solution that makes all numbers equal, minimizes their sum, and spends no more than $$$20n$$$ moves.

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

Each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — the number of integers given to Maxim.

It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$5 \cdot 10^4$$$.

## Output Format
For each test case print $$$-1$$$ if it's impossible to make all numbers equal.

Otherwise print a single integer $$$s$$$ ($$$0 \le s \le 20n$$$) — the number of steps. Then print $$$s$$$ lines. The $$$i$$$-th line must contain two integers $$$x_i$$$ and $$$y_i$$$ — numbers that Maxim chooses on the $$$i$$$-th step. The numbers must become equal after all operations.

Don't forget that you not only need to make all numbers equal, but also minimize their sum. It is guaranteed that under the given constraints, if a solution exists, then there exists a solution that makes all numbers equal, minimizes their sum, and spends no more than $$$20n$$$ moves.

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

# Problem
You are given a permutation $$$p$$$ of length $$$n$$$.

You can choose any subsequence, remove it from the permutation, and insert it at the beginning of the permutation keeping the same order.

For every $$$k$$$ from $$$0$$$ to $$$n$$$, find the minimal possible number of inversions in the permutation after you choose a subsequence of length exactly $$$k$$$.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of the permutation.

The second line of each test case contains the permutation $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case output $$$n + 1$$$ integers. The $$$i$$$-th of them must be the answer for the subsequence length of $$$i - 1$$$.

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

## Note
In the second test case:

- For the length $$$0$$$: $$$[4, 2, 1, 3] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ inversions.
- For the length $$$1$$$: $$$[4, 2, \mathbf{1}, 3] \rightarrow [1, 4, 2, 3]$$$: $$$2$$$ inversions.
- For the length $$$2$$$: $$$[4, \mathbf{2}, \mathbf{1}, 3] \rightarrow [2, 1, 4, 3]$$$, or $$$[4, 2, \mathbf{1}, \textbf{3}] \rightarrow [1, 3, 4, 2]$$$: $$$2$$$ inversions.
- For the length $$$3$$$: $$$[4, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [2, 1, 3, 4]$$$: $$$1$$$ inversion.
- For the length $$$4$$$: $$$[\mathbf{4}, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ inversions.

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 playing a very popular computer game. The next level consists of $$$n$$$ consecutive locations, numbered from $$$1$$$ to $$$n$$$, each of them containing either land or water. It is known that the first and last locations contain land, and for completing the level you have to move from the first location to the last. Also, if you become inside a location with water, you will die, so you can only move between locations with land.

You can jump between adjacent locations for free, as well as no more than once jump from any location with land $$$i$$$ to any location with land $$$i + x$$$, spending $$$x$$$ coins ($$$x \geq 0$$$).

Your task is to spend the minimum possible number of coins to move from the first location to the last one.

Note that this is always possible since both the first and last locations are the land locations.

## Input Format
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of locations.

The second line of the test case contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), where $$$a_i = 1$$$ means that the $$$i$$$-th location is the location with land, and $$$a_i = 0$$$ means that the $$$i$$$-th location is the location with water. It is guaranteed that $$$a_1 = 1$$$ and $$$a_n = 1$$$.

## Output Format
For each test case print a single integer — the answer to the problem.

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

## Note
In the first test case, it is enough to make one free jump from the first location to the second one, which is also the last one, so the answer is $$$0$$$.

In the second test case, the only way to move from the first location to the last one is to jump between them, which will cost $$$4$$$ coins.

In the third test case, you can jump from the first location to the third for $$$2$$$ coins, and then jump to the fourth location for free, so the answer is $$$2$$$. It can be shown that this is the optimal way.

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
Daniel is watching a football team playing a game during their training session. They want to improve their passing skills during that session.

The game involves $$$n$$$ players, making multiple passes towards each other. Unfortunately, since the balls were moving too fast, after the session Daniel is unable to know how many balls were involved during the game. The only thing he knows is the number of passes delivered by each player during all the session.

Find the minimum possible amount of balls that were involved in the game.

## Input Format
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of players.

The second line of the test case contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$), where $$$a_i$$$ is the number of passes delivered by the $$$i$$$-th player.

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

## Output Format
For each test case print a single integer — the answer to the problem.

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

## Note
In the first test case, with the only ball, the game can go like this:

$$$2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2$$$.

In the second test case, there is no possible way to play the game with only one ball. One possible way to play with two balls:

$$$2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$.

$$$2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$

In the third example, there were no passes, so $$$0$$$ balls are possible.

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
Recently, your friend discovered one special operation on an integer array $$$a$$$:

1. Choose two indices $$$i$$$ and $$$j$$$ ($$$i \neq j$$$);
2. Set $$$a_i = a_j = |a_i - a_j|$$$.

After playing with this operation for a while, he came to the next conclusion:

- For every array $$$a$$$ of $$$n$$$ integers, where $$$1 \le a_i \le 10^9$$$, you can find a pair of indices $$$(i, j)$$$ such that the total sum of $$$a$$$ will decrease after performing the operation.

This statement sounds fishy to you, so you want to find a counterexample for a given integer $$$n$$$. Can you find such counterexample and prove him wrong?

In other words, find an array $$$a$$$ consisting of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) such that for all pairs of indices $$$(i, j)$$$ performing the operation won't decrease the total sum (it will increase or not change the sum).

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

The first and only line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the length of array $$$a$$$.

## Output Format
For each test case, if there is no counterexample array $$$a$$$ of size $$$n$$$, print NO.

Otherwise, print YES followed by the array $$$a$$$ itself ($$$1 \le a_i \le 10^9$$$). If there are multiple counterexamples, print any.

## Examples
```input
3
2
512
3
```
```output
YES
1 337
NO
YES
31 4 159
```

## Note
In the first test case, the only possible pairs of indices are $$$(1, 2)$$$ and $$$(2, 1)$$$.

If you perform the operation on indices $$$(1, 2)$$$ (or $$$(2, 1)$$$), you'll get $$$a_1 = a_2 = |1 - 337| = 336$$$, or array $$$[336, 336]$$$. In both cases, the total sum increases, so this array $$$a$$$ is a counterexample.

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

# Problem
Let's denote the size of the maximum matching in a graph $$$G$$$ as $$$\mathit{MM}(G)$$$.

You are given a bipartite graph. The vertices of the first part are numbered from $$$1$$$ to $$$n$$$, the vertices of the second part are numbered from $$$n+1$$$ to $$$2n$$$. Each vertex's degree is $$$2$$$.

For a tuple of four integers $$$(l, r, L, R)$$$, where $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$, let's define $$$G'(l, r, L, R)$$$ as the graph which consists of all vertices of the given graph that are included in the segment $$$[l, r]$$$ or in the segment $$$[L, R]$$$, and all edges of the given graph such that each of their endpoints belongs to one of these segments. In other words, to obtain $$$G'(l, r, L, R)$$$ from the original graph, you have to remove all vertices $$$i$$$ such that $$$i \notin [l, r]$$$ and $$$i \notin [L, R]$$$, and all edges incident to these vertices.

Calculate the sum of $$$\mathit{MM}(G(l, r, L, R))$$$ over all tuples of integers $$$(l, r, L, R)$$$ having $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 1500$$$) — the number of vertices in each part.

Then $$$2n$$$ lines follow, each denoting an edge of the graph. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$n + 1 \le y_i \le 2n$$$) — the endpoints of the $$$i$$$-th edge.

There are no multiple edges in the given graph, and each vertex has exactly two incident edges.

## Output Format
Print one integer — the sum of $$$\mathit{MM}(G(l, r, L, R))$$$ over all tuples of integers $$$(l, r, L, R)$$$ having $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$.

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

Now solve the problem and return the code.