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

# Problem
There are $$$n$$$ programmers choosing their favorite algorithm amongst $$$m$$$ different choice options. Before the first round, all $$$m$$$ options are available. In each round, every programmer makes a vote for one of the remaining algorithms. After the round, only the algorithms with the maximum number of votes remain. The voting process ends when there is only one option left. Determine whether the voting process can continue indefinitely or no matter how people vote, they will eventually choose a single option after some finite amount of rounds?

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

Each test case consists of a single line containing two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^6$$$) — the number of people and choice options respectively.

## Output Format
For each test case output "YES" if the programmers will eventually choose a single option, and "NO" otherwise.

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as a positive answer).

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

## Note
In the first example, there are $$$8$$$ ways people could vote: $$$\{1|1|1, 1|1|2, 1|2|1, 1|2|2, 2|1|1, 2|1|2, 2|2|1, 2|2|2\}$$$.

In cases $$$1$$$, $$$2$$$, $$$3$$$, and $$$5$$$, the programmers are left with the first algorithm, and in the remaining cases people are left with the second one, so the voting ends in one round in any case.

In the second example, the programmers could always vote $$$1|1|2|2$$$. Both algorithms have the maximum number of votes and remain for the next round, so the voting never ends.

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
There is a street with $$$n$$$ sights, with sight number $$$i$$$ being $$$i$$$ miles from the beginning of the street. Sight number $$$i$$$ has beauty $$$b_i$$$. You want to start your morning jog $$$l$$$ miles and end it $$$r$$$ miles from the beginning of the street. By the time you run, you will see sights you run by (including sights at $$$l$$$ and $$$r$$$ miles from the start). You are interested in the $$$3$$$ most beautiful sights along your jog, but every mile you run, you get more and more tired.

So choose $$$l$$$ and $$$r$$$, such that there are at least $$$3$$$ sights you run by, and the sum of beauties of the $$$3$$$ most beautiful sights minus the distance in miles you have to run is maximized. More formally, choose $$$l$$$ and $$$r$$$, such that $$$b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$$$ is maximum possible, where $$$i_1, i_2, i_3$$$ are the indices of the three maximum elements in range $$$[l, r]$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$b_i$$$ ($$$1 \leq b_i \leq 10^8$$$) — beauties of sights $$$i$$$ miles from the beginning of the street.

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$10^5$$$.

## Output Format
For each test case output a single integer equal to the maximum value $$$b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$$$ for some running range $$$[l, r]$$$.

## Examples
```input
4
5
5 1 4 2 3
4
1 1 1 1
6
9 8 7 6 5 4
7
100000000 1 100000000 1 100000000 1 100000000
```
```output
8
1
22
299999996
```

## Note
In the first example, we can choose $$$l$$$ and $$$r$$$ to be $$$1$$$ and $$$5$$$. So we visit all the sights and the three sights with the maximum beauty are the sights with indices $$$1$$$, $$$3$$$, and $$$5$$$ with beauties $$$5$$$, $$$4$$$, and $$$3$$$, respectively. So the total value is $$$5 + 4 + 3 - (5 - 1) = 8$$$.

In the second example, the range $$$[l, r]$$$ can be $$$[1, 3]$$$ or $$$[2, 4]$$$, the total value is $$$1 + 1 + 1 - (3 - 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There is a string $$$a$$$ (unknown to you), consisting of lowercase Latin letters, encrypted according to the following rule into string $$$s$$$:

- after each character of string $$$a$$$, an arbitrary (possibly zero) number of any lowercase Latin letters, different from the character itself, is added;
- after each such addition, the character that we supplemented is added.

You are given string $$$s$$$, and you need to output the initial string $$$a$$$. In other words, you need to decrypt string $$$s$$$.

Note that each string encrypted in this way is decrypted uniquely.

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

The descriptions of the test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of the encrypted message.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ — the encrypted message obtained from some string $$$a$$$.

## Output Format
For each test case, output the decrypted message $$$a$$$ on a separate line.

## Examples
```input
3
8
abacabac
5
qzxcq
20
ccooddeeffoorrcceess
```
```output
ac
q
codeforces
```

## Note
In the first encrypted message, the letter $$$a$$$ is encrypted as $$$aba$$$, and the letter $$$c$$$ is encrypted as $$$cabac$$$.

In the second encrypted message, only one letter $$$q$$$ is encrypted as $$$qzxcq$$$.

In the third encrypted message, zero characters are added to each letter.

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
Dima Vatrushin is a math teacher at school. He was sent on vacation for $$$n$$$ days for his good work. Dima has long dreamed of going to a ski resort, so he wants to allocate several consecutive days and go skiing. Since the vacation requires careful preparation, he will only go for at least $$$k$$$ days.

You are given an array $$$a$$$ containing the weather forecast at the resort. That is, on the $$$i$$$-th day, the temperature will be $$$a_i$$$ degrees.

Dima was born in Siberia, so he can go on vacation only if the temperature does not rise above $$$q$$$ degrees throughout the vacation.

Unfortunately, Dima was so absorbed in abstract algebra that he forgot how to count. He asks you to help him and count the number of ways to choose vacation dates at the resort.

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

Then follow the descriptions of the test cases.

The first line of each test case contains three integers $$$n$$$, $$$k$$$, $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$, $$$-10^9 \le q \le 10^9$$$) — the length of the array $$$a$$$, the minimum number of days at the resort, and the maximum comfortable temperature for Dima.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the temperature at the ski resort.

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

## Output Format
Output $$$t$$$ integers, each of which is the answer to the corresponding test case — the number of ways for Dima to choose vacation dates at the resort.

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

## Note
In the first test case of the example, Dima can go on any day, so the suitable dates for him are [1], [2], [3], [1, 2], [2, 3], [1, 2, 3].

In the second and fourth test cases of the example, Dima cannot go on any day due to the high temperature, so there are no suitable dates.

In the third test case of the example, Dima can only go on the dates [1, 2, 3].

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

# Problem
Rishi is developing games in the 2D metaverse and wants to offer game bundles to his customers. Each game has an associated enjoyment value. A game bundle consists of a subset of games whose total enjoyment value adds up to $$$60$$$.

Your task is to choose $$$k$$$ games, where $$$1 \leq k \leq 60$$$, along with their respective enjoyment values $$$a_1, a_2, \dots, a_k$$$, in such a way that exactly $$$m$$$ distinct game bundles can be formed.

## Input Format
The input is a single integer $$$m$$$ ($$$1 \le m \le 10^{10}$$$) — the desired number of game bundles.

## Output Format
The first line should contain an integer $$$k$$$ ($$$1 \le k \le 60$$$) — the number of games.

The second line should contain $$$k$$$ integers, $$$a_1, a_2, \dots, a_k$$$ ($$$1 \le a_1, a_2, \dots, a_k \le 60$$$) — the enjoyment values of the $$$k$$$ games.

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

## Note
In the first sample, any subset of size $$$3$$$ is a game bundle. There are $$$4$$$ such subsets.

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
A positive integer is called $$$k$$$-beautiful, if the digit sum of the decimal representation of this number is divisible by $$$k^{\dagger}$$$. For example, $$$9272$$$ is $$$5$$$-beautiful, since the digit sum of $$$9272$$$ is $$$9 + 2 + 7 + 2 = 20$$$.

You are given two integers $$$x$$$ and $$$k$$$. Please find the smallest integer $$$y \ge x$$$ which is $$$k$$$-beautiful.

$$$^{\dagger}$$$ An integer $$$n$$$ is divisible by $$$k$$$ if there exists an integer $$$m$$$ such that $$$n = k \cdot m$$$.

## 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 only line of each test case contains two integers $$$x$$$ and $$$k$$$ ($$$1 \le x \le 10^9$$$, $$$1 \le k \le 10$$$).

## Output Format
For each test case, output the smallest integer $$$y \ge x$$$ which is $$$k$$$-beautiful.

## Examples
```input
6
1 5
10 8
37 9
777 3
1235 10
1 10
```
```output
5
17
45
777
1243
19
```

## Note
In the first test case, numbers from $$$1$$$ to $$$4$$$ consist of a single digit, thus the digit sum is equal to the number itself. None of the integers from $$$1$$$ to $$$4$$$ are divisible by $$$5$$$.

In the fourth test case, the digit sum of $$$777$$$ is $$$7 + 7 + 7 = 21$$$ which is already divisible by $$$3$$$.

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

# Problem
The array $$$a_1, a_2, \ldots, a_m$$$ is initially filled with zeroes. You are given $$$n$$$ pairwise distinct segments $$$1 \le l_i \le r_i \le m$$$. You have to select an arbitrary subset of these segments (in particular, you may select an empty set). Next, you do the following:

- For each $$$i = 1, 2, \ldots, n$$$, if the segment $$$(l_i, r_i)$$$ has been selected to the subset, then for each index $$$l_i \le j \le r_i$$$ you increase $$$a_j$$$ by $$$1$$$ (i. e. $$$a_j$$$ is replaced by $$$a_j + 1$$$). If the segment $$$(l_i, r_i)$$$ has not been selected, the array does not change.
- Next (after processing all values of $$$i = 1, 2, \ldots, n$$$), you compute $$$\max(a)$$$ as the maximum value among all elements of $$$a$$$. Analogously, compute $$$\min(a)$$$ as the minimum value.
- Finally, the cost of the selected subset of segments is declared as $$$\max(a) - \min(a)$$$.

Please, find the maximum cost among all subsets of segments.

## 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$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$) — the number of segments and the length of the array.

The following $$$n$$$ lines of each test case describe the segments. The $$$i$$$-th of these lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$). It is guaranteed that the segments are pairwise distinct.

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

## Output Format
For each test case, output the maximum cost among all subsets of the given set of segments.

## Examples
```input
6
1 3
2 2
3 8
2 4
3 5
4 6
6 3
1 1
1 2
1 3
2 2
2 3
3 3
7 6
2 2
1 6
1 2
5 6
1 5
4 4
3 6
6 27
6 26
5 17
2 3
20 21
1 22
12 24
4 1000000000
2 999999999
3 1000000000
123456789 987654321
9274 123456789
```
```output
1
3
2
3
4
4
```

## Note
In the first test case, there is only one segment available. If we do not select it, then the array will be $$$a = [0, 0, 0]$$$, and the cost of such (empty) subset of segments will be $$$0$$$. If, however, we select the only segment, the array will be $$$a = [0, 1, 0]$$$, and the cost will be $$$1 - 0 = 1$$$.

In the second test case, we can select all the segments: the array will be $$$a = [0, 1, 2, 3, 2, 1, 0, 0]$$$ in this case. The cost will be $$$3 - 0 = 3$$$.

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$$$.

A pair of integers $$$(i, j)$$$, such that $$$1 \le i < j \le n$$$, is called good, if there does not exist an integer $$$k$$$ ($$$1 \le k \le n$$$) such that $$$a_i$$$ is divisible by $$$a_k$$$ and $$$a_j$$$ is divisible by $$$a_k$$$ at the same time.

Please, find the number of good pairs.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

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

## Output Format
For each test case, output the number of good pairs.

## Examples
```input
6
4
2 4 4 4
4
2 3 4 4
9
6 8 9 4 6 8 9 4 9
9
7 7 4 4 9 9 6 2 9
18
10 18 18 15 14 4 5 6 8 9 10 12 15 16 18 17 13 11
21
12 19 19 18 18 12 2 18 19 12 12 3 12 12 12 18 19 16 18 19 12
```
```output
0
3
26
26
124
82
```

## Note
In the first test case, there are no good pairs.

In the second test case, here are all the good pairs: $$$(1, 2)$$$, $$$(2, 3)$$$, and $$$(2, 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 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
Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:

- After the cutting each ribbon piece should have length a, b or c.
- After the cutting the number of ribbon pieces should be maximum.

Help Polycarpus and find the number of ribbon pieces after the required cutting.

## Input Format
The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.

## Output Format
Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

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

## Note
In the first example Polycarpus can cut the ribbon in such way: the first piece has length 2, the second piece has length 3.

In the second example Polycarpus can cut the ribbon in such way: the first piece has length 5, the second piece has length 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 have two positive integers w and h. Your task is to count the number of rhombi which have the following properties:

- Have positive area.
- With vertices at integer points.
- All vertices of the rhombi are located inside or on the border of the rectangle with vertices at points (0, 0), (w, 0), (w, h), (0, h). In other words, for all vertices (xi, yi) of the rhombus the following conditions should fulfill: 0 ≤ xi ≤ w and 0 ≤ yi ≤ h.
- Its diagonals are parallel to the axis.

Count the number of such rhombi.

Let us remind you that a rhombus is a quadrilateral whose four sides all have the same length.

## Input Format
The first line contains two integers w and h (1 ≤ w, h ≤ 4000) — the rectangle's sizes.

## Output Format
Print a single number — the number of sought rhombi.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

## Examples
```input
2 2
```
```output
1
```
-----
```input
1 2
```
```output
0
```

## Note
In the first example there exists only one such rhombus. Its vertices are located at points (1, 0), (2, 1), (1, 2), (0, 1).

Now solve the problem and return the code.