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

# Problem
Oleg received a permutation $$$a$$$ of length $$$n$$$ as a birthday present.

Oleg's friend Nechipor asks Oleg $$$q$$$ questions, each question is characterized by two numbers $$$l$$$ and $$$r$$$, in response to the question Oleg must say the number of sets of indices $$$(t_1, t_2, \ldots, t_k)$$$ of any length $$$k \ge 1$$$ such that:

- $$$l \le t_i \le r$$$ for each $$$i$$$ from $$$1$$$ to $$$k$$$.
- $$$t_i < t_{i+1}$$$ for each $$$i$$$ from $$$1$$$ to $$$k-1$$$.
- $$$a_{t_{i+1}}$$$ is divisible by $$$a_{t_i}$$$ for each $$$i$$$ from $$$1$$$ to $$$k-1$$$.

Help Oleg and answer all of Nechipor's questions.

## Input Format
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of sets of input data. The description of the sets of input data follows.

The first line of each set of input data contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — the length of the permutation and the number of Nechipor's questions.

The second line of each set of input data contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the permutation $$$a$$$ itself.

In each of the next $$$q$$$ lines of each set of input data, there are two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the next question of Nechipor.

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

## Output Format
For each set of input data, output the answers to all of Nechipor's questions.

## Examples
```input
4
8 8
2 1 6 3 5 4 8 7
1 8
2 8
1 7
1 6
1 3
5 8
4 4
2 3
1 1
1
1 1
3 3
3 2 1
1 2
1 3
2 3
8 1
1 2 3 4 5 6 7 8
1 8
```
```output
20 15 18 12 5 5 1 3
1
2 3 2
27
```

## Note
All suitable arrays in the first set of input data: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 3$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 6, 7$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 5$$$), ($$$2, 6$$$), ($$$2, 7$$$), ($$$2, 8$$$), ($$$2, 6, 7$$$), ($$$6, 7$$$).

All suitable arrays in the fourth set of input data: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 2$$$), ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 5$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 8$$$), ($$$1, 2, 4$$$), ($$$1, 2, 6$$$), ($$$1, 2, 8$$$), ($$$1, 2, 4, 8$$$), ($$$1, 3, 6$$$), ($$$1, 4, 8$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$2, 8$$$), ($$$2, 4, 8$$$), ($$$3, 6$$$), ($$$4, 8$$$).

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
The little boy Nikita was given some cubes as a present. He decided to build a tower out of them.

Initially, the tower doesn't have any cubes. In one move, Nikita either puts exactly $$$1$$$ cube on top of the tower or removes exactly $$$1$$$ cube from the top of the tower. Is it possible that after $$$n$$$ moves, the resulting tower has exactly $$$m$$$ cubes?

## Input Format
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$).

## Output Format
For each test case, output "Yes" (without quotes) if Nikita can obtain a tower with $$$m$$$ cubes, and "No" (without quotes) otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

## Examples
```input
3
3 3
2 4
5 3
```
```output
Yes
No
Yes
```

## Note
In the first test case, Nikita can put $$$1$$$ cube on top of the tower $$$3$$$ times in a row, so the answer is "Yes".

In the second test case, Nikita can only end up with either a tower with no blocks or a tower with $$$2$$$ blocks, so the answer is "No".

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 a positive integer $$$x$$$. Find any array of integers $$$a_0, a_1, \ldots, a_{n-1}$$$ for which the following holds:

- $$$1 \le n \le 32$$$,
- $$$a_i$$$ is $$$1$$$, $$$0$$$, or $$$-1$$$ for all $$$0 \le i \le n - 1$$$,
- $$$x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}}$$$,
- There does not exist an index $$$0 \le i \le n - 2$$$ such that both $$$a_{i} \neq 0$$$ and $$$a_{i + 1} \neq 0$$$.

It can be proven that under the constraints of the problem, a valid array always exists.

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

The only line of each test case contains a single positive integer $$$x$$$ ($$$1 \le x < 2^{30}$$$).

## Output Format
For each test case, output two lines.

On the first line, output an integer $$$n$$$ ($$$1 \le n \le 32$$$) — the length of the array $$$a_0, a_1, \ldots, a_{n-1}$$$.

On the second line, output the array $$$a_0, a_1, \ldots, a_{n-1}$$$.

If there are multiple valid arrays, you can output any of them.

## Examples
```input
7
1
14
24
15
27
11
19
```
```output
1
1
5
0 -1 0 0 1
6
0 0 0 -1 0 1
5
-1 0 0 0 1
6
-1 0 -1 0 0 1
5
-1 0 -1 0 1
5
-1 0 1 0 1
```

## Note
In the first test case, one valid array is $$$[1]$$$, since $$$(1) \cdot 2^0 = 1$$$.

In the second test case, one possible valid array is $$$[0,-1,0,0,1]$$$, since $$$(0) \cdot 2^0 + (-1) \cdot 2^1 + (0) \cdot 2^2 + (0) \cdot 2^3 + (1) \cdot 2^4 = -2 + 16 = 14$$$.

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
Nikita is a student passionate about number theory and algorithms. He faces an interesting problem related to an array of numbers.

Suppose Nikita has an array of integers $$$a$$$ of length $$$n$$$. He will call a subsequence$$$^\dagger$$$ of the array special if its least common multiple (LCM) is not contained in $$$a$$$. The LCM of an empty subsequence is equal to $$$0$$$.

Nikita wonders: what is the length of the longest special subsequence of $$$a$$$? Help him answer this question!

$$$^\dagger$$$ A sequence $$$b$$$ is a subsequence of $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements, without changing the order of the remaining elements. For example, $$$[5,2,3]$$$ is a subsequence of $$$[1,5,7,8,2,4,3]$$$.

## Input Format
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases. The description of the test cases follows.

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

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

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 integer — the length of the longest special subsequence of $$$a$$$.

## Examples
```input
6
5
1 2 4 8 16
6
3 2 10 20 60 1
7
2 3 4 6 12 100003 1200036
9
2 42 7 3 6 7 7 1 6
8
4 99 57 179 10203 2 11 40812
1
1
```
```output
0
4
4
5
8
0
```

## Note
In the first test case, the LCM of any non-empty subsequence is contained in $$$a$$$, so the answer is $$$0$$$.

In the second test case, we can take the subsequence $$$[3, 2, 10, 1]$$$, its LCM is equal to $$$30$$$, which is not contained in $$$a$$$.

In the third test case, we can take the subsequence $$$[2, 3, 6, 100\,003]$$$, its LCM is equal to $$$600\,018$$$, which is not contained in $$$a$$$.

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 three points with integer coordinates $$$x_1$$$, $$$x_2$$$, and $$$x_3$$$ on the $$$X$$$ axis ($$$1 \leq x_i \leq 10$$$). You can choose any point with an integer coordinate $$$a$$$ on the $$$X$$$ axis. Note that the point $$$a$$$ may coincide with $$$x_1$$$, $$$x_2$$$, or $$$x_3$$$. Let $$$f(a)$$$ be the total distance from the given points to the point $$$a$$$. Find the smallest value of $$$f(a)$$$.

The distance between points $$$a$$$ and $$$b$$$ is equal to $$$|a - b|$$$. For example, the distance between points $$$a = 5$$$ and $$$b = 2$$$ is $$$3$$$.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases. Then follows their descriptions.

The single line of each test case contains three integers $$$x_1$$$, $$$x_2$$$, and $$$x_3$$$ ($$$1 \leq x_i \leq 10$$$) — the coordinates of the points.

## Output Format
For each test case, output the smallest value of $$$f(a)$$$.

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

## Note
In the first test case, the smallest value of $$$f(a)$$$ is achieved when $$$a = 1$$$: $$$f(1) = |1 - 1| + |1 - 1| + |1 - 1| = 0$$$.

In the second test case, the smallest value of $$$f(a)$$$ is achieved when $$$a = 5$$$: $$$f(5) = |1 - 5| + |5 - 5| + |9 - 5| = 8$$$.

In the third test case, the smallest value of $$$f(a)$$$ is achieved when $$$a = 8$$$: $$$f(8) = |8 - 8| + |2 - 8| + |8 - 8| = 6$$$.

In the fourth test case, the smallest value of $$$f(a)$$$ is achieved when $$$a = 9$$$: $$$f(10) = |10 - 9| + |9 - 9| + |3 - 9| = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$k$$$. You need to make it beautiful with the least amount of operations.

Before applying operations, you can shuffle the array elements as you like. For one operation, you can do the following:

- Choose an index $$$1 \leq i \leq n$$$,
- Make $$$a_i = a_i + k$$$.

The array $$$b_1, b_2, \ldots, b_n$$$ is beautiful if $$$b_i = b_{n - i + 1}$$$ for all $$$1 \leq i \leq n$$$.

Find the minimum number of operations needed to make the array beautiful, or report that it is impossible.

## Input Format
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 10^9$$$) — the size of the array $$$a$$$ and the number $$$k$$$ from the problem statement.

The second line of each set of input data contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all sets of input data does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each set of input data, output the minimum number of operations needed to make the array beautiful, or $$$-1$$$ if it is impossible.

## Examples
```input
11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5
```
```output
0
83966524
1
4
6
1
48
-1
0
14
0
```

## Note
In the first set of input data, the array is already beautiful.

In the second set of input data, you can shuffle the array before the operations and perform the operation with index $$$i = 1$$$ for $$$83966524$$$ times.

In the third set of input data, you can shuffle the array $$$a$$$ and make it equal to $$$[2, 3, 1]$$$. Then apply the operation with index $$$i = 3$$$ to get the array $$$[2, 3, 2]$$$, which is beautiful.

In the eighth set of input data, there is no set of operations and no way to shuffle the elements to make the array beautiful.

In the ninth set of input data, the array is already beautiful.

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

# Problem
This is the hard version of the problem. The only difference is that in this version $$$n \leq 5 \cdot 10^5$$$ and the sum of $$$n$$$ for all sets of input data does not exceed $$$5 \cdot 10^5$$$.

You are given a permutation $$$p$$$ of length $$$n$$$. Calculate the number of index pairs $$$1 \leq i < j \leq n$$$ such that $$$p_i \cdot p_j$$$ is divisible by $$$i \cdot j$$$ without remainder.

A permutation is a sequence of $$$n$$$ integers, in which each integer from $$$1$$$ to $$$n$$$ occurs exactly once. For example, $$$[1]$$$, $$$[3,5,2,1,4]$$$, $$$[1,3,2]$$$ are permutations, while $$$[2,3,2]$$$, $$$[4,3,1]$$$, $$$[0]$$$ are not.

## Input Format
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the length of the permutation $$$p$$$.

The second line of each set of input data contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ for all sets of input data does not exceed $$$5 \cdot 10^5$$$.

## Output Format
For each set of input data, output the number of index pairs $$$1 \leq i < j \leq n$$$ such that $$$p_i \cdot p_j$$$ is divisible by $$$i \cdot j$$$ without remainder.

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

## Note
In the first set of input data, there are no index pairs, as the size of the permutation is $$$1$$$.

In the second set of input data, there is one index pair $$$(1, 2)$$$ and it is valid.

In the third set of input data, the index pair $$$(1, 2)$$$ is valid.

In the fourth set of input data, the index pairs $$$(1, 2)$$$, $$$(1, 5)$$$, and $$$(2, 5)$$$ are valid.

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
Kmes has written three integers $$$a$$$, $$$b$$$ and $$$c$$$ in order to remember that he has to give Noobish_Monk $$$a \times b \times c$$$ bananas.

Noobish_Monk has found these integers and decided to do the following at most $$$5$$$ times:

- pick one of these integers;
- increase it by $$$1$$$.

For example, if $$$a = 2$$$, $$$b = 3$$$ and $$$c = 4$$$, then one can increase $$$a$$$ three times by one and increase $$$b$$$ two times. After that $$$a = 5$$$, $$$b = 5$$$, $$$c = 4$$$. Then the total number of bananas will be $$$5 \times 5 \times 4 = 100$$$.

What is the maximum value of $$$a \times b \times c$$$ Noobish_Monk can achieve with these operations?

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

The first and only line of each test case contains three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10$$$) — Kmes's integers.

## Output Format
For each test case, output a single integer — the maximum amount of bananas Noobish_Monk can get.

## Examples
```input
2
2 3 4
10 1 10
```
```output
100
600
```

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
To celebrate his recovery, k1o0n has baked an enormous $$$n$$$ metres long potato casserole.

Turns out, Noobish_Monk just can't stand potatoes, so he decided to ruin k1o0n's meal. He has cut it into $$$k$$$ pieces, of lengths $$$a_1, a_2, \dots, a_k$$$ meters.

k1o0n wasn't keen on that. Luckily, everything can be fixed. In order to do that, k1o0n can do one of the following operations:

- Pick a piece with length $$$a_i \ge 2$$$ and divide it into two pieces with lengths $$$1$$$ and $$$a_i - 1$$$. As a result, the number of pieces will increase by $$$1$$$;
- Pick a slice $$$a_i$$$ and another slice with length $$$a_j=1$$$ ($$$i \ne j$$$) and merge them into one piece with length $$$a_i+1$$$. As a result, the number of pieces will decrease by $$$1$$$.

Help k1o0n to find the minimum number of operations he needs to do in order to merge the casserole into one piece with length $$$n$$$.

For example, if $$$n=5$$$, $$$k=2$$$ and $$$a = [3, 2]$$$, it is optimal to do the following:

1. Divide the piece with length $$$2$$$ into two pieces with lengths $$$2-1=1$$$ and $$$1$$$, as a result $$$a = [3, 1, 1]$$$.
2. Merge the piece with length $$$3$$$ and the piece with length $$$1$$$, as a result $$$a = [4, 1]$$$.
3. Merge the piece with length $$$4$$$ and the piece with length $$$1$$$, as a result $$$a = [5]$$$.

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

Description of each test case consists of two lines. The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$, $$$2 \le k \le 10^5$$$) — length of casserole and the number of pieces.

The second line contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_i \le n - 1$$$, $$$\sum a_i = n$$$) — lengths of pieces of casserole, which Noobish_Monk has cut.

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

## Output Format
For each test case, output the minimum number of operations K1o0n needs to restore his pie after the terror of Noobish_Monk.

## Examples
```input
4
5 3
3 1 1
5 2
3 2
11 4
2 3 1 5
16 6
1 6 1 1 1 6
```
```output
2
3
9
15
```

Now solve the problem and return the code.