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

# Problem
There are some rabbits in Singapore Zoo. To feed them, Zookeeper bought $$$n$$$ carrots with lengths $$$a_1, a_2, a_3, \ldots, a_n$$$. However, rabbits are very fertile and multiply very quickly. Zookeeper now has $$$k$$$ rabbits and does not have enough carrots to feed all of them. To solve this problem, Zookeeper decided to cut the carrots into $$$k$$$ pieces. For some reason, all resulting carrot lengths must be positive integers.

Big carrots are very difficult for rabbits to handle and eat, so the time needed to eat a carrot of size $$$x$$$ is $$$x^2$$$.

Help Zookeeper split his carrots while minimizing the sum of time taken for rabbits to eat the carrots.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq k \leq 10^5)$$$: the initial number of carrots and the number of rabbits.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^6)$$$: lengths of carrots.

It is guaranteed that the sum of $$$a_i$$$ is at least $$$k$$$.

## Output Format
Output one integer: the minimum sum of time taken for rabbits to eat carrots.

## Examples
```input
3 6
5 3 1
```
```output
15
```
-----
```input
1 4
19
```
```output
91
```

## Note
For the first test, the optimal sizes of carrots are $$$\{1,1,1,2,2,2\}$$$. The time taken is $$$1^2+1^2+1^2+2^2+2^2+2^2=15$$$

For the second test, the optimal sizes of carrots are $$$\{4,5,5,5\}$$$. The time taken is $$$4^2+5^2+5^2+5^2=91$$$.

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
Zookeeper is buying a carton of fruit to feed his pet wabbit. The fruits are a sequence of apples and oranges, which is represented by a binary string $$$s_1s_2\ldots s_n$$$ of length $$$n$$$. $$$1$$$ represents an apple and $$$0$$$ represents an orange.

Since wabbit is allergic to eating oranges, Zookeeper would like to find the longest contiguous sequence of apples. Let $$$f(l,r)$$$ be the longest contiguous sequence of apples in the substring $$$s_{l}s_{l+1}\ldots s_{r}$$$.

Help Zookeeper find $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$$, or the sum of $$$f$$$ across all substrings.

## Input Format
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$.

The next line contains a binary string $$$s$$$ of length $$$n$$$ $$$(s_i \in \{0,1\})$$$

## Output Format
Print a single integer: $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$$.

## Examples
```input
4
0110
```
```output
12
```
-----
```input
7
1101001
```
```output
30
```
-----
```input
12
011100011100
```
```output
156
```

## Note
In the first test, there are ten substrings. The list of them (we let $$$[l,r]$$$ be the substring $$$s_l s_{l+1} \ldots s_r$$$):

- $$$[1,1]$$$: 0
- $$$[1,2]$$$: 01
- $$$[1,3]$$$: 011
- $$$[1,4]$$$: 0110
- $$$[2,2]$$$: 1
- $$$[2,3]$$$: 11
- $$$[2,4]$$$: 110
- $$$[3,3]$$$: 1
- $$$[3,4]$$$: 10
- $$$[4,4]$$$: 0

The lengths of the longest contiguous sequence of ones in each of these ten substrings are $$$0,1,2,2,1,2,2,1,1,0$$$ respectively. Hence, the answer is $$$0+1+2+2+1+2+2+1+1+0 = 12$$$.

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

# Problem
You are given an integer $$$k$$$ and $$$n$$$ distinct points with integer coordinates on the Euclidean plane, the $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$.

Consider a list of all the $$$\frac{n(n - 1)}{2}$$$ pairs of points $$$((x_i, y_i), (x_j, y_j))$$$ ($$$1 \le i < j \le n$$$). For every such pair, write out the distance from the line through these two points to the origin $$$(0, 0)$$$.

Your goal is to calculate the $$$k$$$-th smallest number among these distances.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le \frac{n(n - 1)}{2}$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^4 \le x_i, y_i \le 10^4$$$)  — the coordinates of the $$$i$$$-th point. It is guaranteed that all given points are pairwise distinct.

## Output Format
You should output one number — the $$$k$$$-th smallest distance from the origin. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

## Examples
```input
4 3
2 1
-2 -1
0 -1
-2 4
```
```output
0.707106780737
```

## Note
There are $$$6$$$ pairs of points:

- Line $$$1-2$$$ : distance $$$0$$$ from the origin
- Line $$$1-3$$$ : distance $$$\frac{\sqrt{2}}{2} \approx 0.707106781$$$ from the origin
- Line $$$1-4$$$ : distance $$$2$$$ from the origin
- Line $$$2-3$$$ : distance $$$1$$$ from the origin
- Line $$$2-4$$$ : distance $$$2$$$ from the origin
- Line $$$3-4$$$ : distance $$$\frac{2}{\sqrt{29}} \approx 0.371390676$$$ from the origin

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 playing a new computer game in which you have to fight monsters. In a dungeon you are trying to clear, you met three monsters; the first of them has $$$a$$$ health points, the second has $$$b$$$ health points, and the third has $$$c$$$.

To kill the monsters, you can use a cannon that, when fired, deals $$$1$$$ damage to the selected monster. Every $$$7$$$-th (i. e. shots with numbers $$$7$$$, $$$14$$$, $$$21$$$ etc.) cannon shot is enhanced and deals $$$1$$$ damage to all monsters, not just one of them. If some monster's current amount of health points is $$$0$$$, it can't be targeted by a regular shot and does not receive damage from an enhanced shot.

You want to pass the dungeon beautifully, i. e., kill all the monsters with the same enhanced shot (i. e. after some enhanced shot, the health points of each of the monsters should become equal to $$$0$$$ for the first time). Each shot must hit a monster, i. e. each shot deals damage to at least one monster.

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

Each test case consists of a single line that contains three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^8$$$) — the number of health points each monster has.

## Output Format
For each test case, print YES if you can kill all the monsters with the same enhanced shot. Otherwise, print NO. You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

## Examples
```input
3
3 2 4
1 1 1
10 1 7
```
```output
YES
NO
NO
```

## Note
In the first test case, you can do as follows: $$$1$$$-th shot to the first monster, $$$2$$$-th shot to the second monster, $$$3$$$-th shot to the third monster, $$$4$$$-th shot to the first monster, $$$5$$$-th shot to the third monster, $$$6$$$-th shot to the third monster, and $$$7$$$-th enhanced shot will kill all the monsters.

In the second test case, you can't kill monsters with the same enhanced shot, because the total number of health points of monsters is $$$3$$$, and you will kill them in the first 3 shots.

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 $$$[a_1, a_2, \dots, a_n]$$$ such that $$$1 \le a_i \le 10^9$$$. Let $$$S$$$ be the sum of all elements of the array $$$a$$$.

Let's call an array $$$b$$$ of $$$n$$$ integers beautiful if:

- $$$1 \le b_i \le 10^9$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$;
- for every pair of adjacent integers from the array $$$(b_i, b_{i + 1})$$$, either $$$b_i$$$ divides $$$b_{i + 1}$$$, or $$$b_{i + 1}$$$ divides $$$b_i$$$ (or both);
- $$$2 \sum \limits_{i = 1}^{n} |a_i - b_i| \le S$$$.

Your task is to find any beautiful array. It can be shown that at least one beautiful array always exists.

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

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$).

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

## Output Format
For each test case, print the beautiful array $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) on a separate line. It can be shown that at least one beautiful array exists under these circumstances. If there are multiple answers, print any of them.

## Examples
```input
4
5
1 2 3 4 5
2
4 6
2
1 1000000000
6
3 4 8 1 2 3
```
```output
3 3 3 3 3
3 6
1 1000000000
4 4 8 1 3 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 have $$$2n$$$ integers $$$1, 2, \dots, 2n$$$. You have to redistribute these $$$2n$$$ elements into $$$n$$$ pairs. After that, you choose $$$x$$$ pairs and take minimum elements from them, and from the other $$$n - x$$$ pairs, you take maximum elements.

Your goal is to obtain the set of numbers $$$\{b_1, b_2, \dots, b_n\}$$$ as the result of taking elements from the pairs.

What is the number of different $$$x$$$-s ($$$0 \le x \le n$$$) such that it's possible to obtain the set $$$b$$$ if for each $$$x$$$ you can choose how to distribute numbers into pairs and from which $$$x$$$ pairs choose minimum elements?

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

The first line of each test case contains the integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_1 < b_2 < \dots < b_n \le 2n$$$) — the set you'd like to get.

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

## Output Format
For each test case, print one number — the number of different $$$x$$$-s such that it's possible to obtain the set $$$b$$$.

## Examples
```input
3
1
1
5
1 4 5 9 10
2
3 4
```
```output
1
3
1
```

## Note
In the first test case, $$$x = 1$$$ is the only option: you have one pair $$$(1, 2)$$$ and choose the minimum from this pair.

In the second test case, there are three possible $$$x$$$-s. If $$$x = 1$$$, then you can form the following pairs: $$$(1, 6)$$$, $$$(2, 4)$$$, $$$(3, 5)$$$, $$$(7, 9)$$$, $$$(8, 10)$$$. You can take minimum from $$$(1, 6)$$$ (equal to $$$1$$$) and the maximum elements from all other pairs to get set $$$b$$$.

If $$$x = 2$$$, you can form pairs $$$(1, 2)$$$, $$$(3, 4)$$$, $$$(5, 6)$$$, $$$(7, 9)$$$, $$$(8, 10)$$$ and take the minimum elements from $$$(1, 2)$$$, $$$(5, 6)$$$ and the maximum elements from the other pairs.

If $$$x = 3$$$, you can form pairs $$$(1, 3)$$$, $$$(4, 6)$$$, $$$(5, 7)$$$, $$$(2, 9)$$$, $$$(8, 10)$$$ and take the minimum elements from $$$(1, 3)$$$, $$$(4, 6)$$$, $$$(5, 7)$$$.

In the third test case, $$$x = 0$$$ is the only option: you can form pairs $$$(1, 3)$$$, $$$(2, 4)$$$ and take the maximum elements from both of them.

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

# Problem
Let's call the set of positive integers $$$S$$$ correct if the following two conditions are met:

- $$$S \subseteq \{1, 2, \dots, n\}$$$;
- if $$$a \in S$$$ and $$$b \in S$$$, then $$$|a-b| \neq x$$$ and $$$|a-b| \neq y$$$.

For the given values $$$n$$$, $$$x$$$, and $$$y$$$, you have to find the maximum size of the correct set.

## Input Format
A single line contains three integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le x, y \le 22$$$).

## Output Format
Print one integer — the maximum size of the correct set.

## Examples
```input
10 2 5
```
```output
5
```
-----
```input
21 4 6
```
```output
9
```
-----
```input
1337 7 7
```
```output
672
```
-----
```input
455678451 22 17
```
```output
221997195
```

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
Nezzar buys his favorite snack — $$$n$$$ chocolate bars with lengths $$$l_1,l_2,\ldots,l_n$$$. However, chocolate bars might be too long to store them properly!

In order to solve this problem, Nezzar designs an interesting process to divide them into small pieces. Firstly, Nezzar puts all his chocolate bars into a black box. Then, he will perform the following operation repeatedly until the maximum length over all chocolate bars does not exceed $$$k$$$.

- Nezzar picks a chocolate bar from the box with probability proportional to its length $$$x$$$.
- After step $$$1$$$, Nezzar uniformly picks a real number $$$r \in (0,x)$$$ and divides the chosen chocolate bar into two chocolate bars with lengths $$$r$$$ and $$$x-r$$$.
- Lastly, he puts those two new chocolate bars into the black box.

Nezzar now wonders, what is the expected number of operations he will perform to divide his chocolate bars into small pieces.

It can be shown that the answer can be represented as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not \equiv 0$$$ ($$$\bmod 998\,244\,353$$$). Print the value of $$$P\cdot Q^{-1} \mod 998\,244\,353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 50, 1 \le k \le 2000$$$).

The second line contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i$$$, $$$\sum_{i=1}^{n} l_i \le 2000$$$).

## Output Format
Print a single integer — the expected number of operations Nezzar will perform to divide his chocolate bars into small pieces modulo $$$998\,244\,353$$$.

## Examples
```input
1 1
2
```
```output
4
```
-----
```input
1 1
1
```
```output
0
```
-----
```input
1 5
1234
```
```output
15630811
```
-----
```input
2 1
2 3
```
```output
476014684
```
-----
```input
10 33
10 20 30 40 50 60 70 80 90 100
```
```output
675105648
```

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 have $$$n$$$ stacks of blocks. The $$$i$$$-th stack contains $$$h_i$$$ blocks and it's height is the number of blocks in it. In one move you can take a block from the $$$i$$$-th stack (if there is at least one block) and put it to the $$$i + 1$$$-th stack. Can you make the sequence of heights strictly increasing?

Note that the number of stacks always remains $$$n$$$: stacks don't disappear when they have $$$0$$$ blocks.

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

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 100)$$$. The second line of each test case contains $$$n$$$ integers $$$h_i$$$ $$$(0 \leq h_i \leq 10^9)$$$ — starting heights of the stacks.

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

## Output Format
For each test case output YES if you can make the sequence of heights strictly increasing and NO otherwise.

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

## Examples
```input
6
2
1 2
2
1 0
3
4 4 4
2
0 0
3
0 1 0
4
1000000000 1000000000 1000000000 1000000000
```
```output
YES
YES
YES
NO
NO
YES
```

## Note
In the first test case there is no need to make any moves, the sequence of heights is already increasing.

In the second test case we need to move one block from the first stack to the second. Then the heights become $$$0$$$ $$$1$$$.

In the third test case we could move one block from the first stack to the second and then from the second to the third, which would make the heights $$$3$$$ $$$4$$$ $$$5$$$.

In the fourth test case we can't make a move, but the sequence is not increasing, so the answer is NO.

In the fifth test case we can only make one move (from the second to the third stack), which would make the heights $$$0$$$ $$$0$$$ $$$1$$$. Both $$$0$$$ $$$1$$$ $$$0$$$ and $$$0$$$ $$$0$$$ $$$1$$$ are not increasing sequences, 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 and your friends live in $$$n$$$ houses. Each house is located on a 2D plane, in a point with integer coordinates. There might be different houses located in the same point. The mayor of the city is asking you for places for the building of the Eastern exhibition. You have to find the number of places (points with integer coordinates), so that the summary distance from all the houses to the exhibition is minimal. The exhibition can be built in the same point as some house. The distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is $$$|x_1 - x_2| + |y_1 - y_2|$$$, where $$$|x|$$$ is the absolute value of $$$x$$$.

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

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 1000)$$$. Next $$$n$$$ lines describe the positions of the houses $$$(x_i, y_i)$$$ $$$(0 \leq x_i, y_i \leq 10^9)$$$.

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$1000$$$.

## Output Format
For each test case output a single integer - the number of different positions for the exhibition. The exhibition can be built in the same point as some house.

## Examples
```input
6
3
0 0
2 0
1 2
4
1 0
0 2
2 3
3 1
4
0 0
0 1
1 0
1 1
2
0 0
1 1
2
0 0
2 0
2
0 0
0 0
```
```output
1
4
4
4
3
1
```

## Note
Here are the images for the example test cases. Blue dots stand for the houses, green — possible positions for the exhibition.

First test case.

Second test case.

Third test case.

Fourth test case.

Fifth test case.

Sixth test case. Here both houses are located at $$$(0, 0)$$$.

Now solve the problem and return the code.