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

# Problem
The hobbits Frodo and Sam are carrying the One Ring to Mordor. In order not to be spotted by orcs, they decided to go through the mountains.

The mountain relief can be represented as a polyline with $$$n$$$ points $$$(x_i, y_i)$$$, numbered from $$$1$$$ to $$$n$$$ ($$$x_i < x_{i + 1}$$$ for $$$1 \le i \le n - 1$$$). Hobbits start their journey at the point $$$(x_1, y_1)$$$ and should reach the point $$$(x_n, y_n)$$$ to complete their mission.

The problem is that there is a tower with the Eye of Sauron, which watches them. The tower is located at the point $$$(x_n, y_n)$$$ and has the height $$$H$$$, so the Eye is located at the point $$$(x_n, y_n + H)$$$. In order to complete the mission successfully, the hobbits have to wear cloaks all the time when the Sauron Eye can see them, i. e. when there is a direct line from the Eye to the hobbits which is not intersected by the relief.

The hobbits are low, so their height can be considered negligibly small, but still positive, so when a direct line from the Sauron Eye to the hobbits only touches the relief, the Eye can see them.

The Sauron Eye can't see hobbits when they are in the left position, but can see them when they are in the right position.

The hobbits do not like to wear cloaks, so they wear them only when they can be spotted by the Eye. Your task is to calculate the total distance the hobbits have to walk while wearing cloaks.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$H$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le H \le 10^4$$$) — the number of vertices in polyline and the tower height.

The next $$$n$$$ lines contain two integers $$$x_i, y_i$$$ each ($$$0 \le x_i \le 4 \cdot 10^5$$$; $$$0 \le y_i \le 10^4$$$) — the coordinates of the polyline vertices. It is guaranteed that $$$x_i < x_{i + 1}$$$ for $$$1 \le i \le n - 1$$$.

## Output Format
Print one real number — the total distance the hobbits have to walk while wearing cloaks. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$ — formally, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, your answer will be accepted if $$$\dfrac{|a - b|}{\max(1, b)} \le 10^{-6}$$$.

## Examples
```input
6 10
10 40
20 10
25 30
30 15
50 15
65 30
```
```output
70.4034587602
```
-----
```input
9 5
0 0
5 10
15 10
20 0
25 11
30 0
35 10
50 10
60 5
```
```output
27.2787986124
```
-----
```input
2 10000
0 10000
400000 0
```
```output
400124.9804748512
```

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

# Problem
You are given five integers $$$n$$$, $$$dx_1$$$, $$$dy_1$$$, $$$dx_2$$$ and $$$dy_2$$$. You have to select $$$n$$$ distinct pairs of integers $$$(x_i, y_i)$$$ in such a way that, for every possible pair of integers $$$(x, y)$$$, there exists exactly one triple of integers $$$(a, b, i)$$$ meeting the following constraints:

$$$ \begin{cases} x \, = \, x_i + a \cdot dx_1 + b \cdot dx_2, \\ y \, = \, y_i + a \cdot dy_1 + b \cdot dy_2. \end{cases} $$$

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains two integers $$$dx_1$$$ and $$$dy_1$$$ ($$$-10^6 \le dx_1, dy_1 \le 10^6$$$).

The third line contains two integers $$$dx_2$$$ and $$$dy_2$$$ ($$$-10^6 \le dx_2, dy_2 \le 10^6$$$).

## Output Format
If it is impossible to correctly select $$$n$$$ pairs of integers, print NO.

Otherwise, print YES in the first line, and then $$$n$$$ lines, the $$$i$$$-th of which contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$).

If there are multiple solutions, print any of them.

## Examples
```input
4
2 0
0 2
```
```output
YES
0 0
0 1
1 0
1 1
```
-----
```input
5
2 6
1 5
```
```output
NO
```
-----
```input
2
3 4
1 2
```
```output
YES
0 0
0 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: 512.0 MB

# Problem
There is a robot on a checkered field that is endless in all directions. Initially, the robot is located in the cell with coordinates $$$(0, 0)$$$. He will execute commands which are described by a string of capital Latin letters 'L', 'R', 'D', 'U'. When a command is executed, the robot simply moves in the corresponding direction:

- 'L': one cell to the left (the $$$x$$$-coordinate of the current cell decreases by $$$1$$$);
- 'R': one cell to the right (the $$$x$$$-coordinate of the current cell is increased by $$$1$$$);
- 'D': one cell down (the $$$y$$$-coordinate of the current cell decreases by $$$1$$$);
- 'U': one cell up (the $$$y$$$-coordinate of the current cell is increased by $$$1$$$).

Your task is to put an obstacle in one cell of the field so that after executing the commands, the robot will return to the original cell of its path $$$(0, 0)$$$. Of course, an obstacle cannot be placed in the starting cell $$$(0, 0)$$$. It is guaranteed that if the obstacle is not placed, then the robot will not return to the starting cell.

An obstacle affects the movement of the robot in the following way: if it tries to go in a certain direction, and there is an obstacle, then it simply remains in place (the obstacle also remains, that is, it does not disappear).

Find any such cell of the field (other than $$$(0, 0)$$$) that if you put an obstacle there, the robot will return to the cell $$$(0, 0)$$$ after the execution of all commands. If there is no solution, then report it.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

Each test case consists of a single line containing $$$s$$$ — the sequence of commands, which are uppercase Latin letters 'L', 'R', 'D', 'U' only. The length of $$$s$$$ is between $$$1$$$ and $$$5000$$$, inclusive. Additional constraint on $$$s$$$: executing this sequence of commands leads the robot to some cell other than $$$(0, 0)$$$, if there are no obstacles.

The sum of lengths of all $$$s$$$ in a test doesn't exceed $$$5000$$$.

## Output Format
For each test case print a single line:

- if there is a solution, print two integers $$$x$$$ and $$$y$$$ ($$$-10^9 \le x,y \le 10^9$$$) such that an obstacle in $$$(x, y)$$$ will force the robot to return back to the cell $$$(0, 0)$$$;
- otherwise, print two zeroes (i. e. 0 0).

If there are multiple answers, you can print any of them.

## Examples
```input
4
L
RUUDL
LLUU
DDDUUUUU
```
```output
-1 0
1 2
0 0
0 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: 512.0 MB

# Problem
Suppose you have a sequence of $$$k$$$ integers $$$A = [a_1, a_2, \dots , a_k]$$$ where each $$$a_i \geq 2$$$. A sequence of prime integers $$$P = [p_1, p_2, \dots, p_k]$$$ is called suitable for the sequence $$$A$$$ if $$$a_1$$$ is divisible by $$$p_1$$$, $$$a_2$$$ is divisible by $$$p_2$$$ and so on.

A sequence of prime integers $$$P$$$ is called friendly if there are no unique integers in this sequence.

A sequence $$$A$$$ is called ideal, if each sequence $$$P$$$ that is suitable for $$$A$$$ is friendly as well (i. e. there is no sequence $$$P$$$ that is suitable for $$$A$$$, but not friendly). For example, the sequence $$$[2, 4, 16]$$$ is ideal, while the sequence $$$[2, 4, 6]$$$ is not ideal (there exists a sequence $$$P = [2, 2, 3]$$$ which is suitable for $$$A$$$, but not friendly).

You are given $$$n$$$ different integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$. You have to choose exactly $$$k$$$ of them in such a way that they form an ideal sequence, or report that it is impossible. Note that no integer can be chosen more than once.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 1000$$$).

The second line contains $$$n$$$ pairwise distinct integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ ($$$2 \leq x_i \leq 10^{18}$$$).

## Output Format
If it is impossible to choose exactly $$$k$$$ integers from $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ in such a way that the chosen integers form an ideal sequence, print $$$0$$$.

Otherwise, print $$$k$$$ pairwise distinct integers — the elements of the chosen ideal sequence. If there are multiple answers, print any of them.

## Examples
```input
3 3
2 4 6
```
```output
0
```
-----
```input
3 3
2 4 16
```
```output
2 4 16
```
-----
```input
4 3
2 4 6 16
```
```output
2 4 16
```

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

# Problem
You are given $$$n$$$ sets of integers. The $$$i$$$-th set contains $$$k_i$$$ integers.

Two sets are called similar if they share at least two common elements, i. e. there exist two integers $$$x$$$ and $$$y$$$ such that $$$x \ne y$$$, and they both belong to each of the two sets.

Your task is to find two similar sets among the given ones, or report that there is no such pair of sets.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) the number of given sets. The following $$$n$$$ lines describe the sets. The $$$i$$$-th line starts with an integer $$$k_i$$$ ($$$2 \le k_i \le 10^5$$$) — the number of integers in the $$$i$$$-th set. Then $$$k_i$$$ integers $$$a_{i,1}$$$, $$$a_{i,2}$$$, ..., $$$a_{i,k_i}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) follow — the elements of the $$$i$$$-th set. It is guaranteed that all elements in each set are different.

The total number of elements in all sets in all test cases is not greater than $$$2\cdot 10^5$$$.

## Output Format
For each test case, print the answer on a single line.

If there is no pair of similar sets, print -1.

Otherwise, print two different integers — the indices of the similar sets. The sets are numbered from $$$1$$$ to $$$n$$$ in the order they are given in the input. If there are multiple answers, print any of them.

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

# Problem
You are given $$$n$$$ points on a plane.

Please find the minimum sum of areas of two axis-aligned rectangles, such that each point is contained in at least one of these rectangles.

Note that the chosen rectangles can be degenerate. Rectangle contains all the points that lie inside it or on its boundary.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$)  — the number of test cases.

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

The following $$$n$$$ lines contain the coordinates of the points $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^9$$$). It is guaranteed that the points are distinct.

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

## Output Format
For each test case print one integer — the minimum sum of areas.

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

## Note
In the first two test cases the answer consists of 2 degenerate rectangles. In the third test case one of the possible answers consists of two rectangles $$$1 \times 1$$$ with bottom left corners $$$(0,0)$$$ and $$$(9,9)$$$.

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
One day you wanted to read something, so you went to your bookshelf to grab some book. But when you saw how messy the bookshelf was you decided to clean it up first.

There are $$$n$$$ books standing in a row on the shelf, the $$$i$$$-th book has color $$$a_i$$$.

You'd like to rearrange the books to make the shelf look beautiful. The shelf is considered beautiful if all books of the same color are next to each other.

In one operation you can take one book from any position on the shelf and move it to the right end of the shelf.

What is the minimum number of operations you need to make the shelf beautiful?

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of books.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the book colors.

## Output Format
Output the minimum number of operations to make the shelf beautiful.

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

## Note
In the first example, we have the bookshelf $$$[1, 2, 2, 1, 3]$$$ and can, for example:

1. take a book on position $$$4$$$ and move to the right end: we'll get $$$[1, 2, 2, 3, 1]$$$;
2. take a book on position $$$1$$$ and move to the right end: we'll get $$$[2, 2, 3, 1, 1]$$$.

In the second example, we can move the first book to the end of the bookshelf and get $$$[2,2,1,1,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
Kilani and Abd are neighbors for 3000 years, but then the day came and Kilani decided to move to another house. As a farewell gift, Kilani is going to challenge Abd with a problem written by their other neighbor with the same name Abd.

The problem is:

You are given a connected tree rooted at node $$$1$$$.

You should assign a character a or b to every node in the tree so that the total number of a's is equal to $$$x$$$ and the total number of b's is equal to $$$n - x$$$.

Let's define a string for each node $$$v$$$ of the tree as follows:

- if $$$v$$$ is root then the string is just one character assigned to $$$v$$$:
- otherwise, let's take a string defined for the $$$v$$$'s parent $$$p_v$$$ and add to the end of it a character assigned to $$$v$$$.

You should assign every node a character in a way that minimizes the number of distinct strings among the strings of all nodes.

## Input Format
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 10^5$$$; $$$0 \leq x \leq n$$$) — the number of vertices in the tree the number of a's.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, \dots, p_{n}$$$ ($$$1 \leq p_i \leq n$$$; $$$p_i \neq i$$$), where $$$p_i$$$ is the parent of node $$$i$$$.

It is guaranteed that the input describes a connected tree.

## Output Format
In the first line, print the minimum possible total number of distinct strings.

In the second line, print $$$n$$$ characters, where all characters are either a or b and the $$$i$$$-th character is the character assigned to the $$$i$$$-th node.

Make sure that the total number of a's is equal to $$$x$$$ and the total number of b's is equal to $$$n - x$$$.

If there is more than one answer you can print any of them.

## Examples
```input
9 3
1 2 2 4 4 4 3 1
```
```output
4
aabbbbbba
```

## Note
The tree from the sample is shown below:

The tree after assigning characters to every node (according to the output) is the following:

Strings for all nodes are the following:

- string of node $$$1$$$ is: a
- string of node $$$2$$$ is: aa
- string of node $$$3$$$ is: aab
- string of node $$$4$$$ is: aab
- string of node $$$5$$$ is: aabb
- string of node $$$6$$$ is: aabb
- string of node $$$7$$$ is: aabb
- string of node $$$8$$$ is: aabb
- string of node $$$9$$$ is: aa

The set of unique strings is $$$\{\text{a}, \text{aa}, \text{aab}, \text{aabb}\}$$$, so the number of distinct strings is $$$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 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 have a board represented as a grid with $$$2 \times n$$$ cells.

The first $$$k_1$$$ cells on the first row and first $$$k_2$$$ cells on the second row are colored in white. All other cells are colored in black.

You have $$$w$$$ white dominoes ($$$2 \times 1$$$ tiles, both cells are colored in white) and $$$b$$$ black dominoes ($$$2 \times 1$$$ tiles, both cells are colored in black).

You can place a white domino on the board if both board's cells are white and not occupied by any other domino. In the same way, you can place a black domino if both cells are black and not occupied by any other domino.

Can you place all $$$w + b$$$ dominoes on the board if you can place dominoes both horizontally and vertically?

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

The first line of each test case contains three integers $$$n$$$, $$$k_1$$$ and $$$k_2$$$ ($$$1 \le n \le 1000$$$; $$$0 \le k_1, k_2 \le n$$$).

The second line of each test case contains two integers $$$w$$$ and $$$b$$$ ($$$0 \le w, b \le n$$$).

## Output Format
For each test case, print YES if it's possible to place all $$$w + b$$$ dominoes on the board and NO, otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

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

## Note
In the first test case, $$$n = 1$$$, $$$k_1 = 0$$$ and $$$k_2 = 1$$$. It means that $$$2 \times 1$$$ board has black cell $$$(1, 1)$$$ and white cell $$$(2, 1)$$$. So, you can't place any white domino, since there is only one white cell.

In the second test case, the board of the same size $$$2 \times 1$$$, but both cell are white. Since $$$w = 0$$$ and $$$b = 0$$$, so you can place $$$0 + 0 = 0$$$ dominoes on the board.

In the third test case, board $$$2 \times 3$$$, but fully colored in black (since $$$k_1 = k_2 = 0$$$), so you can't place any white domino.

In the fourth test case, cells $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, and $$$(2, 1)$$$ are white and other cells are black. You can place $$$2$$$ white dominoes at positions $$$((1, 1), (2, 1))$$$ and $$$((1, 2), (1, 3))$$$ and $$$2$$$ black dominoes at positions $$$((1, 4), (2, 4))$$$ $$$((2, 2), (2, 3))$$$.

Now solve the problem and return the code.