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
Adilbek was assigned to a special project. For Adilbek it means that he has $$$n$$$ days to run a special program and provide its results. But there is a problem: the program needs to run for $$$d$$$ days to calculate the results.

Fortunately, Adilbek can optimize the program. If he spends $$$x$$$ ($$$x$$$ is a non-negative integer) days optimizing the program, he will make the program run in $$$\left\lceil \frac{d}{x + 1} \right\rceil$$$ days ($$$\left\lceil a \right\rceil$$$ is the ceiling function: $$$\left\lceil 2.4 \right\rceil = 3$$$, $$$\left\lceil 2 \right\rceil = 2$$$). The program cannot be run and optimized simultaneously, so the total number of days he will spend is equal to $$$x + \left\lceil \frac{d}{x + 1} \right\rceil$$$.

Will Adilbek be able to provide the generated results in no more than $$$n$$$ days?

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

The next $$$T$$$ lines contain test cases – one per line. Each line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le d \le 10^9$$$) — the number of days before the deadline and the number of days the program runs.

## Output Format
Print $$$T$$$ answers — one per test case. For each test case print YES (case insensitive) if Adilbek can fit in $$$n$$$ days or NO (case insensitive) otherwise.

## Examples
```input
3
1 1
4 5
5 11
```
```output
YES
YES
NO
```

## Note
In the first test case, Adilbek decides not to optimize the program at all, since $$$d \le n$$$.

In the second test case, Adilbek can spend $$$1$$$ day optimizing the program and it will run $$$\left\lceil \frac{5}{2} \right\rceil = 3$$$ days. In total, he will spend $$$4$$$ days and will fit in the limit.

In the third test case, it's impossible to fit in the limit. For example, if Adilbek will optimize the program $$$2$$$ days, it'll still work $$$\left\lceil \frac{11}{2+1} \right\rceil = 4$$$ days.

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 given two integers $$$A$$$ and $$$B$$$, calculate the number of pairs $$$(a, b)$$$ such that $$$1 \le a \le A$$$, $$$1 \le b \le B$$$, and the equation $$$a \cdot b + a + b = conc(a, b)$$$ is true; $$$conc(a, b)$$$ is the concatenation of $$$a$$$ and $$$b$$$ (for example, $$$conc(12, 23) = 1223$$$, $$$conc(100, 11) = 10011$$$). $$$a$$$ and $$$b$$$ should not contain leading zeroes.

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

Each test case contains two integers $$$A$$$ and $$$B$$$ $$$(1 \le A, B \le 10^9)$$$.

## Output Format
Print one integer — the number of pairs $$$(a, b)$$$ such that $$$1 \le a \le A$$$, $$$1 \le b \le B$$$, and the equation $$$a \cdot b + a + b = conc(a, b)$$$ is true.

## Examples
```input
3
1 11
4 2
191 31415926
```
```output
1
0
1337
```

## Note
There is only one suitable pair in the first test case: $$$a = 1$$$, $$$b = 9$$$ ($$$1 + 9 + 1 \cdot 9 = 19$$$).

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 given two integers $$$n$$$ and $$$m$$$. Calculate the number of pairs of arrays $$$(a, b)$$$ such that:

- the length of both arrays is equal to $$$m$$$;
- each element of each array is an integer between $$$1$$$ and $$$n$$$ (inclusive);
- $$$a_i \le b_i$$$ for any index $$$i$$$ from $$$1$$$ to $$$m$$$;
- array $$$a$$$ is sorted in non-descending order;
- array $$$b$$$ is sorted in non-ascending order.

As the result can be very large, you should print it modulo $$$10^9+7$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 1000$$$, $$$1 \le m \le 10$$$).

## Output Format
Print one integer – the number of arrays $$$a$$$ and $$$b$$$ satisfying the conditions described above modulo $$$10^9+7$$$.

## Examples
```input
2 2
```
```output
5
```
-----
```input
10 1
```
```output
55
```
-----
```input
723 9
```
```output
157557417
```

## Note
In the first test there are $$$5$$$ suitable arrays:

- $$$a = [1, 1], b = [2, 2]$$$;
- $$$a = [1, 2], b = [2, 2]$$$;
- $$$a = [2, 2], b = [2, 2]$$$;
- $$$a = [1, 1], b = [2, 1]$$$;
- $$$a = [1, 1], b = [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 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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You are given $$$n$$$ arrays $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$; each array consists of exactly $$$m$$$ integers. We denote the $$$y$$$-th element of the $$$x$$$-th array as $$$a_{x, y}$$$.

You have to choose two arrays $$$a_i$$$ and $$$a_j$$$ ($$$1 \le i, j \le n$$$, it is possible that $$$i = j$$$). After that, you will obtain a new array $$$b$$$ consisting of $$$m$$$ integers, such that for every $$$k \in [1, m]$$$ $$$b_k = \max(a_{i, k}, a_{j, k})$$$.

Your goal is to choose $$$i$$$ and $$$j$$$ so that the value of $$$\min \limits_{k = 1}^{m} b_k$$$ is maximum possible.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 8$$$) — the number of arrays and the number of elements in each array, respectively.

Then $$$n$$$ lines follow, the $$$x$$$-th line contains the array $$$a_x$$$ represented by $$$m$$$ integers $$$a_{x, 1}$$$, $$$a_{x, 2}$$$, ..., $$$a_{x, m}$$$ ($$$0 \le a_{x, y} \le 10^9$$$).

## Output Format
Print two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, it is possible that $$$i = j$$$) — the indices of the two arrays you have to choose so that the value of $$$\min \limits_{k = 1}^{m} b_k$$$ is maximum possible. If there are multiple answers, print any of them.

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

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
Polycarp has three sisters: Alice, Barbara, and Cerene. They're collecting coins. Currently, Alice has $$$a$$$ coins, Barbara has $$$b$$$ coins and Cerene has $$$c$$$ coins. Recently Polycarp has returned from the trip around the world and brought $$$n$$$ coins.

He wants to distribute all these $$$n$$$ coins between his sisters in such a way that the number of coins Alice has is equal to the number of coins Barbara has and is equal to the number of coins Cerene has. In other words, if Polycarp gives $$$A$$$ coins to Alice, $$$B$$$ coins to Barbara and $$$C$$$ coins to Cerene ($$$A+B+C=n$$$), then $$$a + A = b + B = c + C$$$.

Note that A, B or C (the number of coins Polycarp gives to Alice, Barbara and Cerene correspondingly) can be 0.

Your task is to find out if it is possible to distribute all $$$n$$$ coins between sisters in a way described above.

You have to answer $$$t$$$ independent test cases.

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

The next $$$t$$$ lines describe test cases. Each test case is given on a new line and consists of four space-separated integers $$$a, b, c$$$ and $$$n$$$ ($$$1 \le a, b, c, n \le 10^8$$$) — the number of coins Alice has, the number of coins Barbara has, the number of coins Cerene has and the number of coins Polycarp has.

## Output Format
For each test case, print "YES" if Polycarp can distribute all $$$n$$$ coins between his sisters and "NO" otherwise.

## Examples
```input
5
5 3 2 8
100 101 102 105
3 2 1 100000000
10 20 15 14
101 101 101 3
```
```output
YES
YES
NO
NO
YES
```

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 rectangular matrix of size $$$n \times m$$$ consisting of integers from $$$1$$$ to $$$2 \cdot 10^5$$$.

In one move, you can:

- choose any element of the matrix and change its value to any integer between $$$1$$$ and $$$n \cdot m$$$, inclusive;
- take any column and shift it one cell up cyclically (see the example of such cyclic shift below).

A cyclic shift is an operation such that you choose some $$$j$$$ ($$$1 \le j \le m$$$) and set $$$a_{1, j} := a_{2, j}, a_{2, j} := a_{3, j}, \dots, a_{n, j} := a_{1, j}$$$ simultaneously.

Example of cyclic shift of the first column

You want to perform the minimum number of moves to make this matrix look like this:

In other words, the goal is to obtain the matrix, where $$$a_{1, 1} = 1, a_{1, 2} = 2, \dots, a_{1, m} = m, a_{2, 1} = m + 1, a_{2, 2} = m + 2, \dots, a_{n, m} = n \cdot m$$$ (i.e. $$$a_{i, j} = (i - 1) \cdot m + j$$$) with the minimum number of moves performed.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5, n \cdot m \le 2 \cdot 10^5$$$) — the size of the matrix.

The next $$$n$$$ lines contain $$$m$$$ integers each. The number at the line $$$i$$$ and position $$$j$$$ is $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 2 \cdot 10^5$$$).

## Output Format
Print one integer — the minimum number of moves required to obtain the matrix, where $$$a_{1, 1} = 1, a_{1, 2} = 2, \dots, a_{1, m} = m, a_{2, 1} = m + 1, a_{2, 2} = m + 2, \dots, a_{n, m} = n \cdot m$$$ ($$$a_{i, j} = (i - 1)m + j$$$).

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

## Note
In the first example, you can set $$$a_{1, 1} := 7, a_{1, 2} := 8$$$ and $$$a_{1, 3} := 9$$$ then shift the first, the second and the third columns cyclically, so the answer is $$$6$$$. It can be shown that you cannot achieve a better answer.

In the second example, the matrix is already good so the answer is $$$0$$$.

In the third example, it is enough to shift the second column cyclically twice to obtain a good matrix, so the answer is $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an unweighted tree with $$$n$$$ vertices. Recall that a tree is a connected undirected graph without cycles.

Your task is to choose three distinct vertices $$$a, b, c$$$ on this tree such that the number of edges which belong to at least one of the simple paths between $$$a$$$ and $$$b$$$, $$$b$$$ and $$$c$$$, or $$$a$$$ and $$$c$$$ is the maximum possible. See the notes section for a better understanding.

The simple path is the path that visits each vertex at most once.

## Input Format
The first line contains one integer number $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

Next $$$n - 1$$$ lines describe the edges of the tree in form $$$a_i, b_i$$$ ($$$1 \le a_i$$$, $$$b_i \le n$$$, $$$a_i \ne b_i$$$). It is guaranteed that given graph is a tree.

## Output Format
In the first line print one integer $$$res$$$ — the maximum number of edges which belong to at least one of the simple paths between $$$a$$$ and $$$b$$$, $$$b$$$ and $$$c$$$, or $$$a$$$ and $$$c$$$.

In the second line print three integers $$$a, b, c$$$ such that $$$1 \le a, b, c \le n$$$ and $$$a \ne, b \ne c, a \ne c$$$.

If there are several answers, you can print any.

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

## Note
The picture corresponding to the first example (and another one correct answer):

If you choose vertices $$$1, 5, 6$$$ then the path between $$$1$$$ and $$$5$$$ consists of edges $$$(1, 2), (2, 3), (3, 4), (4, 5)$$$, the path between $$$1$$$ and $$$6$$$ consists of edges $$$(1, 2), (2, 3), (3, 4), (4, 6)$$$ and the path between $$$5$$$ and $$$6$$$ consists of edges $$$(4, 5), (4, 6)$$$. The union of these paths is $$$(1, 2), (2, 3), (3, 4), (4, 5), (4, 6)$$$ so the answer is $$$5$$$. It can be shown that there is no better answer.

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
To become the king of Codeforces, Kuroni has to solve the following problem.

He is given $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. Help Kuroni to calculate $$$\prod_{1\le i<j\le n} |a_i - a_j|$$$. As result can be very big, output it modulo $$$m$$$.

If you are not familiar with short notation, $$$\prod_{1\le i<j\le n} |a_i - a_j|$$$ is equal to $$$|a_1 - a_2|\cdot|a_1 - a_3|\cdot$$$ $$$\dots$$$ $$$\cdot|a_1 - a_n|\cdot|a_2 - a_3|\cdot|a_2 - a_4|\cdot$$$ $$$\dots$$$ $$$\cdot|a_2 - a_n| \cdot$$$ $$$\dots$$$ $$$\cdot |a_{n-1} - a_n|$$$. In other words, this is the product of $$$|a_i - a_j|$$$ for all $$$1\le i < j \le n$$$.

## Input Format
The first line contains two integers $$$n$$$, $$$m$$$ ($$$2\le n \le 2\cdot 10^5$$$, $$$1\le m \le 1000$$$) — number of numbers and modulo.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

## Output Format
Output the single number — $$$\prod_{1\le i<j\le n} |a_i - a_j| \bmod m$$$.

## Examples
```input
2 10
8 5
```
```output
3
```
-----
```input
3 12
1 4 5
```
```output
0
```
-----
```input
3 7
1 4 9
```
```output
1
```

## Note
In the first sample, $$$|8 - 5| = 3 \equiv 3 \bmod 10$$$.

In the second sample, $$$|1 - 4|\cdot|1 - 5|\cdot|4 - 5| = 3\cdot 4 \cdot 1 = 12 \equiv 0 \bmod 12$$$.

In the third sample, $$$|1 - 4|\cdot|1 - 9|\cdot|4 - 9| = 3 \cdot 8 \cdot 5 = 120 \equiv 1 \bmod 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 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
Kuroni is the coordinator of the next Mathforces round written by the "Proof by AC" team. All the preparation has been done, and he is discussing with the team about the score distribution for the round.

The round consists of $$$n$$$ problems, numbered from $$$1$$$ to $$$n$$$. The problems are ordered in increasing order of difficulty, no two problems have the same difficulty. A score distribution for the round can be denoted by an array $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the score of $$$i$$$-th problem.

Kuroni thinks that the score distribution should satisfy the following requirements:

- The score of each problem should be a positive integer not exceeding $$$10^9$$$.
- A harder problem should grant a strictly higher score than an easier problem. In other words, $$$1 \leq a_1 < a_2 < \dots < a_n \leq 10^9$$$.
- The balance of the score distribution, defined as the number of triples $$$(i, j, k)$$$ such that $$$1 \leq i < j < k \leq n$$$ and $$$a_i + a_j = a_k$$$, should be exactly $$$m$$$.

Help the team find a score distribution that satisfies Kuroni's requirement. In case such a score distribution does not exist, output $$$-1$$$.

## Input Format
The first and single line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5000$$$, $$$0 \leq m \leq 10^9$$$) — the number of problems and the required balance.

## Output Format
If there is no solution, print a single integer $$$-1$$$.

Otherwise, print a line containing $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, representing a score distribution that satisfies all the requirements. If there are multiple answers, print any of them.

## Examples
```input
5 3
```
```output
4 5 9 13 18
```
-----
```input
8 0
```
```output
10 11 12 13 14 15 16 17
```
-----
```input
4 10
```
```output
-1
```

## Note
In the first example, there are $$$3$$$ triples $$$(i, j, k)$$$ that contribute to the balance of the score distribution.

- $$$(1, 2, 3)$$$
- $$$(1, 3, 4)$$$
- $$$(2, 4, 5)$$$

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.5 seconds
Memory limit: 256.0 MB

# Problem
Kuroni is very angry at the other setters for using him as a theme! As a punishment, he forced them to solve the following problem:

You have an array $$$a$$$ consisting of $$$n$$$ positive integers. An operation consists of choosing an element and either adding $$$1$$$ to it or subtracting $$$1$$$ from it, such that the element remains positive. We say the array is good if the greatest common divisor of all its elements is not $$$1$$$. Find the minimum number of operations needed to make the array good.

Unable to match Kuroni's intellect, the setters failed to solve the problem. Help them escape from Kuroni's punishment!

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)  — the number of elements in the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. ($$$1 \le a_i \le 10^{12}$$$)  — the elements of the array.

## Output Format
Print a single integer  — the minimum number of operations required to make the array good.

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

## Note
In the first example, the first array is already good, since the greatest common divisor of all the elements is $$$2$$$.

In the second example, we may apply the following operations:

1. Add $$$1$$$ to the second element, making it equal to $$$9$$$.
2. Subtract $$$1$$$ from the third element, making it equal to $$$6$$$.
3. Add $$$1$$$ to the fifth element, making it equal to $$$2$$$.
4. Add $$$1$$$ to the fifth element again, making it equal to $$$3$$$.

The greatest common divisor of all elements will then be equal to $$$3$$$, so the array will be good. It can be shown that no sequence of three or less operations can make the array good.

Now solve the problem and return the code.