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

# Problem
Harry Potter is hiking in the Alps surrounding Lake Geneva. In this area there are $$$m$$$ cabins, numbered 1 to $$$m$$$. Each cabin is connected, with one or more trails, to a central meeting point next to the lake. Each trail is either short or long. Cabin $$$i$$$ is connected with $$$s_i$$$ short trails and $$$l_i$$$ long trails to the lake.

Each day, Harry walks a trail from the cabin where he currently is to Lake Geneva, and then from there he walks a trail to any of the $$$m$$$ cabins (including the one he started in). However, as he has to finish the hike in a day, at least one of the two trails has to be short.

How many possible combinations of trails can Harry take if he starts in cabin 1 and walks for $$$n$$$ days?

Give the answer modulo $$$10^9 + 7$$$.

## Input Format
The first line contains the integers $$$m$$$ and $$$n$$$.

The second line contains $$$m$$$ integers, $$$s_1, \dots, s_m$$$, where $$$s_i$$$ is the number of short trails between cabin $$$i$$$ and Lake Geneva.

The third and last line contains $$$m$$$ integers, $$$l_1, \dots, l_m$$$, where $$$l_i$$$ is the number of long trails between cabin $$$i$$$ and Lake Geneva.

We have the following constraints:

$$$0 \le s_i, l_i \le 10^3$$$.

$$$1 \le m \le 10^2$$$.

$$$1 \le n \le 10^9$$$.

## Output Format
The number of possible combinations of trails, modulo $$$10^9 + 7$$$.

## Examples
```input
3 2
1 0 1
0 1 1
```
```output
18
```

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
Harry Potter is hiking in the Alps surrounding Lake Geneva. In this area there are $$$m$$$ cabins, numbered 1 to $$$m$$$. Each cabin is connected, with one or more trails, to a central meeting point next to the lake. Each trail is either short or long. Cabin $$$i$$$ is connected with $$$s_i$$$ short trails and $$$l_i$$$ long trails to the lake.

Each day, Harry walks a trail from the cabin where he currently is to Lake Geneva, and then from there he walks a trail to any of the $$$m$$$ cabins (including the one he started in). However, as he has to finish the hike in a day, at least one of the two trails has to be short.

How many possible combinations of trails can Harry take if he starts in cabin 1 and walks for $$$n$$$ days?

Give the answer modulo $$$10^9 + 7$$$.

## Input Format
The first line contains the integers $$$m$$$ and $$$n$$$.

The second line contains $$$m$$$ integers, $$$s_1, \dots, s_m$$$, where $$$s_i$$$ is the number of short trails between cabin $$$i$$$ and Lake Geneva.

The third and last line contains $$$m$$$ integers, $$$l_1, \dots, l_m$$$, where $$$l_i$$$ is the number of long trails between cabin $$$i$$$ and Lake Geneva.

We have the following constraints:

$$$0 \le s_i, l_i \le 10^3$$$.

$$$1 \le m \le 10^5$$$.

$$$1 \le n \le 10^9$$$.

## Output Format
The number of possible combinations of trails, modulo $$$10^9 + 7$$$.

## Examples
```input
3 2
1 0 1
0 1 1
```
```output
18
```

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
Turtle and Piggy are playing a number game.

First, Turtle will choose an integer $$$x$$$, such that $$$l \le x \le r$$$, where $$$l, r$$$ are given. It's also guaranteed that $$$2l \le r$$$.

Then, Piggy will keep doing the following operation until $$$x$$$ becomes $$$1$$$:

- Choose an integer $$$p$$$ such that $$$p \ge 2$$$ and $$$p \mid x$$$ (i.e. $$$x$$$ is a multiple of $$$p$$$).
- Set $$$x$$$ to $$$\frac{x}{p}$$$, and the score will increase by $$$1$$$.

The score is initially $$$0$$$. Both Turtle and Piggy want to maximize the score. Please help them to calculate the maximum score.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$l, r$$$ ($$$1 \le l \le r \le 10^9, 2l \le r$$$) — The range where Turtle can choose the integer from.

## Output Format
For each test case, output a single integer — the maximum score.

## Examples
```input
5
2 4
3 6
2 15
6 22
114514 1919810
```
```output
2
2
3
4
20
```

## Note
In the first test case, Turtle can choose an integer $$$x$$$, such that $$$2 \le x \le 4$$$. He can choose $$$x = 4$$$. Then Piggy can choose $$$p = 2$$$ for $$$2$$$ times. After that, $$$x$$$ will become $$$1$$$, and the score will be $$$2$$$, which is maximized.

In the second test case, Turtle can choose an integer $$$3 \le x \le 6$$$. He can choose $$$x = 6$$$. Then Piggy can choose $$$p = 2$$$, then choose $$$p = 3$$$. After that, $$$x$$$ will become $$$1$$$, and the score will be $$$2$$$, which is maximum.

In the third test case, Turtle can choose $$$x = 12$$$.

In the fourth test case, Turtle can choose $$$x = 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: 256.0 MB

# Problem
There is a sequence $$$a_0, a_1, a_2, \ldots$$$ of infinite length. Initially $$$a_i = i$$$ for every non-negative integer $$$i$$$.

After every second, each element of the sequence will simultaneously change. $$$a_i$$$ will change to $$$a_{i - 1} \mid a_i \mid a_{i + 1}$$$ for every positive integer $$$i$$$. $$$a_0$$$ will change to $$$a_0 \mid a_1$$$. Here, $$$|$$$ denotes bitwise OR.

Turtle is asked to find the value of $$$a_n$$$ after $$$m$$$ seconds. In particular, if $$$m = 0$$$, then he needs to find the initial value of $$$a_n$$$. He is tired of calculating so many values, so please help him!

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ ($$$0 \le n, m \le 10^9$$$).

## Output Format
For each test case, output a single integer — the value of $$$a_n$$$ after $$$m$$$ seconds.

## Examples
```input
9
0 0
0 1
0 2
1 0
5 2
10 1
20 3
1145 14
19198 10
```
```output
0
1
3
1
7
11
23
1279
19455
```

## Note
After $$$1$$$ second, $$$[a_0, a_1, a_2, a_3, a_4, a_5]$$$ will become $$$[1, 3, 3, 7, 7, 7]$$$.

After $$$2$$$ seconds, $$$[a_0, a_1, a_2, a_3, a_4, a_5]$$$ will become $$$[3, 3, 7, 7, 7, 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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Turtle just learned how to multiply two integers in his math class, and he was very excited.

Then Piggy gave him an integer $$$n$$$, and asked him to construct a sequence $$$a_1, a_2, \ldots, a_n$$$ consisting of integers which satisfied the following conditions:

- For all $$$1 \le i \le n$$$, $$$1 \le a_i \le 3 \cdot 10^5$$$.
- For all $$$1 \le i < j \le n - 1$$$, $$$a_i \cdot a_{i + 1} \ne a_j \cdot a_{j + 1}$$$.

Of all such sequences, Piggy asked Turtle to find the one with the minimum number of distinct elements.

Turtle definitely could not solve the problem, so please help him!

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

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

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

## Output Format
For each test case, output $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the elements of the sequence $$$a$$$.

If there are multiple answers, print any of them.

## Examples
```input
3
2
3
4
```
```output
114514 114514
1 2 2
3 3 4 4
```

## Note
In the third test case, $$$a = [3, 4, 2, 6]$$$ violates the second condition since $$$a_1 \cdot a_2 = a_3 \cdot a_4$$$. $$$a = [2, 3, 4, 4]$$$ satisfy the conditions but its number of distinct elements isn't minimum.

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
Vitaly503 is given a checkered board with a side of $$$n$$$ and $$$k$$$ chips. He realized that all these $$$k$$$ chips need to be placed on the cells of the board (no more than one chip can be placed on a single cell).

Let's denote the cell in the $$$i$$$-th row and $$$j$$$-th column as $$$(i ,j)$$$. A diagonal is the set of cells for which the value $$$i + j$$$ is the same. For example, cells $$$(3, 1)$$$, $$$(2, 2)$$$, and $$$(1, 3)$$$ lie on the same diagonal, but $$$(1, 2)$$$ and $$$(2, 3)$$$ do not. A diagonal is called occupied if it contains at least one chip.

Determine what is the minimum possible number of occupied diagonals among all placements of $$$k$$$ chips.

## Input Format
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of sets of input data. Then follow the descriptions of the sets of input data.

The only line of each set of input data contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 100, 0 \le k \le n^2$$$) — the side of the checkered board and the number of available chips, respectively.

## Output Format
For each set of input data, output a single integer — the minimum number of occupied diagonals with at least one chip that he can get after placing all $$$k$$$ chips.

## Examples
```input
7
1 0
2 2
2 3
2 4
10 50
100 239
3 9
```
```output
0
1
2
3
6
3
5
```

## Note
In the first test case, there are no chips, so 0 diagonals will be occupied. In the second test case, both chips can be placed on diagonal $$$(2, 1), (1, 2)$$$, so the answer is 1. In the third test case, 3 chips can't be placed on one diagonal, but placing them on $$$(1, 2), (2, 1), (1, 1)$$$ makes 2 diagonals occupied. In the 7th test case, chips will occupy all 5 diagonals in any valid placing.

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
This is the easy version of a problem. The only difference between an easy and a hard version is the constraints on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous $$$2 n$$$ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $$$2 i - 1$$$ is sitting at the desk with the knight $$$2 i$$$.

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the $$$i$$$-th knight as $$$a_i$$$. Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize $$$\max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i})$$$.

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform $$$a_i := a_{i + n}$$$, $$$a_{i + n} := a_i$$$ for any $$$1 \le i \le n$$$. Arthur can make any number of such swaps. What is the best result he can achieve?

## Input Format
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of desks.

The second line consists of $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — the intelligence values of the knights.

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

## Output Format
For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

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

## Note
In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be $$$10$$$.

In the third test case, Arthur can make $$$0$$$ operations, which will result in the total intelligence of $$$11$$$ at each of the desks.

In the fourth test case, Arthur can swap knights with indices $$$2$$$ and $$$5$$$ and achieve the difference of $$$2$$$. It can be proven that he cannot improve his result any further.

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
This is the hard version of a problem. The only difference between an easy and a hard version is the constraints on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous $$$2 n$$$ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $$$2 i - 1$$$ is sitting at the desk with the knight $$$2 i$$$.

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the $$$i$$$-th knight as $$$a_i$$$. Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize $$$\max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i})$$$.

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform $$$a_i := a_{i + n}$$$, $$$a_{i + n} := a_i$$$ for any $$$1 \le i \le n$$$. Arthur can make any number of such swaps. What is the best result he can achieve?

## Input Format
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100\,000$$$) — the number of desks.

The second line consists of $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — the intelligence values of the knights.

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

## Output Format
For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

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

## Note
In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be $$$10$$$.

In the third test case, Arthur can make $$$0$$$ operations, which will result in the total intelligence of $$$11$$$ at each of the desks.

In the fourth test case, Arthur can swap knights with indices $$$2$$$ and $$$5$$$ and achieve the difference of $$$2$$$. It can be proven that he cannot improve his result any further.

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

# Problem
There is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that

- starts in the upper left cell of the matrix;
- each following cell is to the right or down from the current cell;
- the way ends in the bottom right cell.

Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.

## Input Format
The first line contains an integer number n (2 ≤ n ≤ 1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding 109).

## Output Format
In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.

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

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

# Problem
The Olympic Games in Bercouver are in full swing now. Here everyone has their own objectives: sportsmen compete for medals, and sport commentators compete for more convenient positions to give a running commentary. Today the main sport events take place at three round stadiums, and the commentator's objective is to choose the best point of observation, that is to say the point from where all the three stadiums can be observed. As all the sport competitions are of the same importance, the stadiums should be observed at the same angle. If the number of points meeting the conditions is more than one, the point with the maximum angle of observation is prefered.

Would you, please, help the famous Berland commentator G. Berniev to find the best point of observation. It should be noted, that the stadiums do not hide each other, the commentator can easily see one stadium through the other.

## Input Format
The input data consists of three lines, each of them describes the position of one stadium. The lines have the format x,  y,  r, where (x, y) are the coordinates of the stadium's center ( -  103 ≤ x,  y ≤ 103), and r (1 ≤ r  ≤ 103) is its radius. All the numbers in the input data are integer, stadiums do not have common points, and their centers are not on the same line.

## Output Format
Print the coordinates of the required point with five digits after the decimal point. If there is no answer meeting the conditions, the program shouldn't print anything. The output data should be left blank.

## Examples
```input
0 0 10
60 0 10
30 30 10
```
```output
30.00000 0.00000
```

Now solve the problem and return the code.