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
Allen wants to enter a fan zone that occupies a round square and has $$$n$$$ entrances.

There already is a queue of $$$a_i$$$ people in front of the $$$i$$$-th entrance. Each entrance allows one person from its queue to enter the fan zone in one minute.

Allen uses the following strategy to enter the fan zone:

- Initially he stands in the end of the queue in front of the first entrance.
- Each minute, if he is not allowed into the fan zone during the minute (meaning he is not the first in the queue), he leaves the current queue and stands in the end of the queue of the next entrance (or the first entrance if he leaves the last entrance).

Determine the entrance through which Allen will finally enter the fan zone.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of entrances.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the number of people in queues. These numbers do not include Allen.

## Output Format
Print a single integer — the number of entrance that Allen will use.

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

## Note
In the first example the number of people (not including Allen) changes as follows: $$$[\textbf{2}, 3, 2, 0] \to [1, \textbf{2}, 1, 0] \to [0, 1, \textbf{0}, 0]$$$. The number in bold is the queue Alles stands in. We see that he will enter the fan zone through the third entrance.

In the second example the number of people (not including Allen) changes as follows: $$$[\textbf{10}, 10] \to [9, \textbf{9}] \to [\textbf{8}, 8] \to [7, \textbf{7}] \to [\textbf{6}, 6] \to \\ [5, \textbf{5}] \to [\textbf{4}, 4] \to [3, \textbf{3}] \to [\textbf{2}, 2] \to [1, \textbf{1}] \to [\textbf{0}, 0]$$$.

In the third example the number of people (not including Allen) changes as follows: $$$[\textbf{5}, 2, 6, 5, 7, 4] \to [4, \textbf{1}, 5, 4, 6, 3] \to [3, 0, \textbf{4}, 3, 5, 2] \to \\ [2, 0, 3, \textbf{2}, 4, 1] \to [1, 0, 2, 1, \textbf{3}, 0] \to [0, 0, 1, 0, 2, \textbf{0}]$$$.

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
Sonya decided that having her own hotel business is the best way of earning money because she can profit and rest wherever she wants.

The country where Sonya lives is an endless line. There is a city in each integer coordinate on this line. She has $$$n$$$ hotels, where the $$$i$$$-th hotel is located in the city with coordinate $$$x_i$$$. Sonya is a smart girl, so she does not open two or more hotels in the same city.

Sonya understands that her business needs to be expanded by opening new hotels, so she decides to build one more. She wants to make the minimum distance from this hotel to all others to be equal to $$$d$$$. The girl understands that there are many possible locations to construct such a hotel. Thus she wants to know the number of possible coordinates of the cities where she can build a new hotel.

Because Sonya is lounging in a jacuzzi in one of her hotels, she is asking you to find the number of cities where she can build a new hotel so that the minimum distance from the original $$$n$$$ hotels to the new one is equal to $$$d$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1\leq n\leq 100$$$, $$$1\leq d\leq 10^9$$$) — the number of Sonya's hotels and the needed minimum distance from a new hotel to all others.

The second line contains $$$n$$$ different integers in strictly increasing order $$$x_1, x_2, \ldots, x_n$$$ ($$$-10^9\leq x_i\leq 10^9$$$) — coordinates of Sonya's hotels.

## Output Format
Print the number of cities where Sonya can build a new hotel so that the minimum distance from this hotel to all others is equal to $$$d$$$.

## Examples
```input
4 3
-3 2 9 16
```
```output
6
```
-----
```input
5 2
4 8 11 18 19
```
```output
5
```

## Note
In the first example, there are $$$6$$$ possible cities where Sonya can build a hotel. These cities have coordinates $$$-6$$$, $$$5$$$, $$$6$$$, $$$12$$$, $$$13$$$, and $$$19$$$.

In the second example, there are $$$5$$$ possible cities where Sonya can build a hotel. These cities have coordinates $$$2$$$, $$$6$$$, $$$13$$$, $$$16$$$, and $$$21$$$.

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 string $$$t$$$ consisting of $$$n$$$ lowercase Latin letters and an integer number $$$k$$$.

Let's define a substring of some string $$$s$$$ with indices from $$$l$$$ to $$$r$$$ as $$$s[l \dots r]$$$.

Your task is to construct such string $$$s$$$ of minimum possible length that there are exactly $$$k$$$ positions $$$i$$$ such that $$$s[i \dots i + n - 1] = t$$$. In other words, your task is to construct such string $$$s$$$ of minimum possible length that there are exactly $$$k$$$ substrings of $$$s$$$ equal to $$$t$$$.

It is guaranteed that the answer is always unique.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 50$$$) — the length of the string $$$t$$$ and the number of substrings.

The second line of the input contains the string $$$t$$$ consisting of exactly $$$n$$$ lowercase Latin letters.

## Output Format
Print such string $$$s$$$ of minimum possible length that there are exactly $$$k$$$ substrings of $$$s$$$ equal to $$$t$$$.

It is guaranteed that the answer is always unique.

## Examples
```input
3 4
aba
```
```output
ababababa
```
-----
```input
3 2
cat
```
```output
catcat
```

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
There is an infinite board of square tiles. Initially all tiles are white.

Vova has a red marker and a blue marker. Red marker can color $$$a$$$ tiles. Blue marker can color $$$b$$$ tiles. If some tile isn't white then you can't use marker of any color on it. Each marker must be drained completely, so at the end there should be exactly $$$a$$$ red tiles and exactly $$$b$$$ blue tiles across the board.

Vova wants to color such a set of tiles that:

- they would form a rectangle, consisting of exactly $$$a+b$$$ colored tiles;
- all tiles of at least one color would also form a rectangle.

Here are some examples of correct colorings:

Here are some examples of incorrect colorings:

Among all correct colorings Vova wants to choose the one with the minimal perimeter. What is the minimal perimeter Vova can obtain?

It is guaranteed that there exists at least one correct coloring.

## Input Format
A single line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^{14}$$$) — the number of tiles red marker should color and the number of tiles blue marker should color, respectively.

## Output Format
Print a single integer — the minimal perimeter of a colored rectangle Vova can obtain by coloring exactly $$$a$$$ tiles red and exactly $$$b$$$ tiles blue.

It is guaranteed that there exists at least one correct coloring.

## Examples
```input
4 4
```
```output
12
```
-----
```input
3 9
```
```output
14
```
-----
```input
9 3
```
```output
14
```
-----
```input
3 6
```
```output
12
```
-----
```input
506 2708
```
```output
3218
```

## Note
The first four examples correspond to the first picture of the statement.

Note that for there exist multiple correct colorings for all of the examples.

In the first example you can also make a rectangle with sides $$$1$$$ and $$$8$$$, though its perimeter will be $$$18$$$ which is greater than $$$8$$$.

In the second example you can make the same resulting rectangle with sides $$$3$$$ and $$$4$$$, but red tiles will form the rectangle with sides $$$1$$$ and $$$3$$$ and blue tiles will form the rectangle with sides $$$3$$$ and $$$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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Once upon a time there was only one router in the well-known company Bmail. Years went by and over time new routers were purchased. Every time they bought a new router, they connected it to one of the routers bought before it. You are given the values $$$p_i$$$ — the index of the router to which the $$$i$$$-th router was connected after being purchased ($$$p_i < i$$$).

There are $$$n$$$ routers in Boogle in total now. Print the sequence of routers on the path from the first to the $$$n$$$-th router.

## Input Format
The first line contains integer number $$$n$$$ ($$$2 \le n \le 200000$$$) — the number of the routers. The following line contains $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$), where $$$p_i$$$ is equal to index of the router to which the $$$i$$$-th was connected after purchase.

## Output Format
Print the path from the $$$1$$$-st to the $$$n$$$-th router. It starts with $$$1$$$ and ends with $$$n$$$. All the elements in the path should be distinct.

## Examples
```input
8
1 1 2 2 3 2 5
```
```output
1 2 5 8
```
-----
```input
6
1 2 3 4 5
```
```output
1 2 3 4 5 6
```
-----
```input
7
1 1 2 3 4 3
```
```output
1 3 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
We get more and more news about DDoS-attacks of popular websites.

Arseny is an admin and he thinks that a website is under a DDoS-attack if the total number of requests for a some period of time exceeds $$$100 \cdot t$$$, where $$$t$$$ — the number of seconds in this time segment.

Arseny knows statistics on the number of requests per second since the server is booted. He knows the sequence $$$r_1, r_2, \dots, r_n$$$, where $$$r_i$$$ — the number of requests in the $$$i$$$-th second after boot.

Determine the length of the longest continuous period of time, which Arseny considers to be a DDoS-attack. A seeking time period should not go beyond the boundaries of the segment $$$[1, n]$$$.

## Input Format
The first line contains $$$n$$$ ($$$1 \le n \le 5000$$$) — number of seconds since server has been booted. The second line contains sequence of integers $$$r_1, r_2, \dots, r_n$$$ ($$$0 \le r_i \le 5000$$$), $$$r_i$$$ — number of requests in the $$$i$$$-th second.

## Output Format
Print the only integer number — the length of the longest time period which is considered to be a DDoS-attack by Arseny. If it doesn't exist print 0.

## Examples
```input
5
100 200 1 1 1
```
```output
3
```
-----
```input
5
1 2 3 4 5
```
```output
0
```
-----
```input
2
101 99
```
```output
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
JATC and his friend Giraffe are currently in their room, solving some problems. Giraffe has written on the board an array $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ of integers, such that $$$1 \le a_1 < a_2 < \ldots < a_n \le 10^3$$$, and then went to the bathroom.

JATC decided to prank his friend by erasing some consecutive elements in the array. Since he doesn't want for the prank to go too far, he will only erase in a way, such that Giraffe can still restore the array using the information from the remaining elements. Because Giraffe has created the array, he's also aware that it's an increasing array and all the elements are integers in the range $$$[1, 10^3]$$$.

JATC wonders what is the greatest number of elements he can erase?

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of elements in the array.

The second line of the input contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_1<a_2<\dots<a_n \le 10^3$$$) — the array written by Giraffe.

## Output Format
Print a single integer — the maximum number of consecutive elements in the array that JATC can erase.

If it is impossible to erase even a single element, print $$$0$$$.

## Examples
```input
6
1 3 4 5 6 9
```
```output
2
```
-----
```input
3
998 999 1000
```
```output
2
```
-----
```input
5
1 2 3 4 5
```
```output
4
```

## Note
In the first example, JATC can erase the third and fourth elements, leaving the array $$$[1, 3, \_, \_, 6, 9]$$$. As you can see, there is only one way to fill in the blanks.

In the second example, JATC can erase the second and the third elements. The array will become $$$[998, \_, \_]$$$. Because all the elements are less than or equal to $$$1000$$$, the array is still can be restored. Note, that he can't erase the first $$$2$$$ elements.

In the third example, JATC can erase the first $$$4$$$ elements. Since all the elements are greater than or equal to $$$1$$$, Giraffe can still restore the array. Note, that he can't erase the last $$$4$$$ elements.

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
JATC's math teacher always gives the class some interesting math problems so that they don't get bored. Today the problem is as follows. Given an integer $$$n$$$, you can perform the following operations zero or more times:

- mul $$$x$$$: multiplies $$$n$$$ by $$$x$$$ (where $$$x$$$ is an arbitrary positive integer).
- sqrt: replaces $$$n$$$ with $$$\sqrt{n}$$$ (to apply this operation, $$$\sqrt{n}$$$ must be an integer).

You can perform these operations as many times as you like. What is the minimum value of $$$n$$$, that can be achieved and what is the minimum number of operations, to achieve that minimum value?

Apparently, no one in the class knows the answer to this problem, maybe you can help them?

## Input Format
The only line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the initial number.

## Output Format
Print two integers: the minimum integer $$$n$$$ that can be achieved using the described operations and the minimum number of operations required.

## Examples
```input
20
```
```output
10 2
```
-----
```input
5184
```
```output
6 4
```

## Note
In the first example, you can apply the operation mul $$$5$$$ to get $$$100$$$ and then sqrt to get $$$10$$$.

In the second example, you can first apply sqrt to get $$$72$$$, then mul $$$18$$$ to get $$$1296$$$ and finally two more sqrt and you get $$$6$$$.

Note, that even if the initial value of $$$n$$$ is less or equal $$$10^6$$$, it can still become greater than $$$10^6$$$ after applying one or more operations.

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 positive integer $$$n$$$ greater or equal to $$$2$$$. For every pair of integers $$$a$$$ and $$$b$$$ ($$$2 \le |a|, |b| \le n$$$), you can transform $$$a$$$ into $$$b$$$ if and only if there exists an integer $$$x$$$ such that $$$1 < |x|$$$ and ($$$a \cdot x = b$$$ or $$$b \cdot x = a$$$), where $$$|x|$$$ denotes the absolute value of $$$x$$$.

After such a transformation, your score increases by $$$|x|$$$ points and you are not allowed to transform $$$a$$$ into $$$b$$$ nor $$$b$$$ into $$$a$$$ anymore.

Initially, you have a score of $$$0$$$. You can start at any integer and transform it as many times as you like. What is the maximum score you can achieve?

## Input Format
A single line contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$) — the given integer described above.

## Output Format
Print an only integer — the maximum score that can be achieved with the transformations. If it is not possible to perform even a single transformation for all possible starting integers, print $$$0$$$.

## Examples
```input
4
```
```output
8
```
-----
```input
6
```
```output
28
```
-----
```input
2
```
```output
0
```

## Note
In the first example, the transformations are $$$2 \rightarrow 4 \rightarrow (-2) \rightarrow (-4) \rightarrow 2$$$.

In the third example, it is impossible to perform even a single transformation.

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
Vova plans to go to the conference by train. Initially, the train is at the point $$$1$$$ and the destination point of the path is the point $$$L$$$. The speed of the train is $$$1$$$ length unit per minute (i.e. at the first minute the train is at the point $$$1$$$, at the second minute — at the point $$$2$$$ and so on).

There are lanterns on the path. They are placed at the points with coordinates divisible by $$$v$$$ (i.e. the first lantern is at the point $$$v$$$, the second is at the point $$$2v$$$ and so on).

There is also exactly one standing train which occupies all the points from $$$l$$$ to $$$r$$$ inclusive.

Vova can see the lantern at the point $$$p$$$ if $$$p$$$ is divisible by $$$v$$$ and there is no standing train at this position ($$$p \not\in [l; r]$$$). Thus, if the point with the lantern is one of the points covered by the standing train, Vova can't see this lantern.

Your problem is to say the number of lanterns Vova will see during the path. Vova plans to go to $$$t$$$ different conferences, so you should answer $$$t$$$ independent queries.

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

Then $$$t$$$ lines follow. The $$$i$$$-th line contains four integers $$$L_i, v_i, l_i, r_i$$$ ($$$1 \le L, v \le 10^9$$$, $$$1 \le l \le r \le L$$$) — destination point of the $$$i$$$-th path, the period of the lantern appearance and the segment occupied by the standing train.

## Output Format
Print $$$t$$$ lines. The $$$i$$$-th line should contain one integer — the answer for the $$$i$$$-th query.

## Examples
```input
4
10 2 3 7
100 51 51 51
1234 1 100 199
1000000000 1 1 1000000000
```
```output
3
0
1134
0
```

## Note
For the first example query, the answer is $$$3$$$. There are lanterns at positions $$$2$$$, $$$4$$$, $$$6$$$, $$$8$$$ and $$$10$$$, but Vova didn't see the lanterns at positions $$$4$$$ and $$$6$$$ because of the standing train.

For the second example query, the answer is $$$0$$$ because the only lantern is at the point $$$51$$$ and there is also a standing train at this point.

For the third example query, the answer is $$$1134$$$ because there are $$$1234$$$ lanterns, but Vova didn't see the lanterns from the position $$$100$$$ to the position $$$199$$$ inclusive.

For the fourth example query, the answer is $$$0$$$ because the standing train covers the whole path.

Now solve the problem and return the code.