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

# Problem
Let's call a sequence $$$b_1, b_2, b_3 \dots, b_{k - 1}, b_k$$$ almost increasing if $$$$$$\min(b_1, b_2) \le \min(b_2, b_3) \le \dots \le \min(b_{k - 1}, b_k).$$$$$$ In particular, any sequence with no more than two elements is almost increasing.

You are given a sequence of integers $$$a_1, a_2, \dots, a_n$$$. Calculate the length of its longest almost increasing subsequence.

You'll be given $$$t$$$ test cases. Solve each test case independently.

Reminder: a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the sequence itself.

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

## Output Format
For each test case, print one integer — the length of the longest almost increasing subsequence.

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

## Note
In the first test case, one of the optimal answers is subsequence $$$1, 2, 7, 2, 2, 3$$$.

In the second and third test cases, the whole sequence $$$a$$$ is already almost increasing.

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

# Problem
Monocarp wants to draw four line segments on a sheet of paper. He wants the $$$i$$$-th segment to have its length equal to $$$a_i$$$ ($$$1 \le i \le 4$$$). These segments can intersect with each other, and each segment should be either horizontal or vertical.

Monocarp wants to draw the segments in such a way that they enclose a rectangular space, and the area of that rectangular space should be maximum possible.

For example, if Monocarp wants to draw four segments with lengths $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$, he can do it the following way:

Here, Monocarp has drawn segments $$$AB$$$ (with length $$$1$$$), $$$CD$$$ (with length $$$2$$$), $$$BC$$$ (with length $$$3$$$) and $$$EF$$$ (with length $$$4$$$). He got a rectangle $$$ABCF$$$ with area equal to $$$3$$$ that is enclosed by the segments.

Calculate the maximum area of a rectangle Monocarp can enclose with four segments.

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

Each test case consists of a single line containing four integers $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$a_4$$$ ($$$1 \le a_i \le 10^4$$$) — the lengths of the segments Monocarp wants to draw.

## Output Format
For each test case, print one integer — the maximum area of a rectangle Monocarp can enclose with four segments (it can be shown that the answer is always an integer).

## Examples
```input
4
1 2 3 4
5 5 5 5
3 1 4 1
100 20 20 100
```
```output
3
25
3
2000
```

## Note
The first test case of the example is described in the statement.

For the second test case, Monocarp can draw the segments $$$AB$$$, $$$BC$$$, $$$CD$$$ and $$$DA$$$ as follows:

Here, Monocarp has drawn segments $$$AB$$$ (with length $$$5$$$), $$$BC$$$ (with length $$$5$$$), $$$CD$$$ (with length $$$5$$$) and $$$DA$$$ (with length $$$5$$$). He got a rectangle $$$ABCD$$$ with area equal to $$$25$$$ that is enclosed by the segments.

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

# Problem
There are $$$n$$$ persons located on a plane. The $$$i$$$-th person is located at the point $$$(x_i, y_i)$$$ and initially looks at the point $$$(u_i, v_i)$$$.

At the same moment of time, all persons will start to rotate clockwise synchronously with the same angular speed. They will rotate until they do one full $$$360$$$-degree turn.

It is said that persons $$$A$$$ and $$$B$$$ made eye contact if person $$$A$$$ looks in person $$$B$$$'s direction at the same moment when person $$$B$$$ looks in person $$$A$$$'s direction. If there is a person $$$C$$$ located between persons $$$A$$$ and $$$B$$$, that will not obstruct $$$A$$$ and $$$B$$$ from making eye contact. A person can make eye contact with more than one person at the same time.

Calculate the number of pairs of persons that will make eye contact at least once during the rotation (including the initial moment).

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of persons. The following $$$n$$$ lines describe persons, each line containing four space-separated integers $$$x_i, y_i, u_i, v_i$$$ ($$$|x_i|, |y_i|, |u_i|, |v_i| \le 10^9$$$; $$$x_i \ne u_i$$$ or $$$y_i \ne v_i$$$), where ($$$x_i, y_i$$$) are the coordinates of the point where the $$$i$$$-th person is located and ($$$u_i$$$, $$$v_i$$$) are the coordinates of the point that the $$$i$$$-th person looks at initially. Each person's location is unique in each test case.

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, print one integer — the number of pairs of persons who will make eye contact at least once during the rotation, including the initial moment.

## Examples
```input
3
2
0 0 0 1
1 0 2 0
3
0 0 1 1
1 1 0 0
1 0 2 0
6
0 0 0 1
1 0 1 2
2 0 2 3
3 0 3 -5
4 0 4 -5
5 0 5 -5
```
```output
0
1
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 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
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 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
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 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: 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 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: 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 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
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 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: 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 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
Positive integer $$$x$$$ is called divisor of positive integer $$$y$$$, if $$$y$$$ is divisible by $$$x$$$ without remainder. For example, $$$1$$$ is a divisor of $$$7$$$ and $$$3$$$ is not divisor of $$$8$$$.

We gave you an integer $$$d$$$ and asked you to find the smallest positive integer $$$a$$$, such that

- $$$a$$$ has at least $$$4$$$ divisors;
- difference between any two divisors of $$$a$$$ is at least $$$d$$$.

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

The first line of each test case contains a single integer $$$d$$$ ($$$1 \leq d \leq 10000$$$).

## Output Format
For each test case print one integer $$$a$$$ — the answer for this test case.

## Examples
```input
2
1
2
```
```output
6
15
```

## Note
In the first test case, integer $$$6$$$ have following divisors: $$$[1, 2, 3, 6]$$$. There are $$$4$$$ of them and the difference between any two of them is at least $$$1$$$. There is no smaller integer with at least $$$4$$$ divisors.

In the second test case, integer $$$15$$$ have following divisors: $$$[1, 3, 5, 15]$$$. There are $$$4$$$ of them and the difference between any two of them is at least $$$2$$$.

The answer $$$12$$$ is INVALID because divisors are $$$[1, 2, 3, 4, 6, 12]$$$. And the difference between, for example, divisors $$$2$$$ and $$$3$$$ is less than $$$d=2$$$.

Now solve the problem and return the code.