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
Being tired of participating in too many Codeforces rounds, Gildong decided to take some rest in a park. He sat down on a bench, and soon he found two rabbits hopping around. One of the rabbits was taller than the other.

He noticed that the two rabbits were hopping towards each other. The positions of the two rabbits can be represented as integer coordinates on a horizontal line. The taller rabbit is currently on position $$$x$$$, and the shorter rabbit is currently on position $$$y$$$ ($$$x \lt y$$$). Every second, each rabbit hops to another position. The taller rabbit hops to the positive direction by $$$a$$$, and the shorter rabbit hops to the negative direction by $$$b$$$.

For example, let's say $$$x=0$$$, $$$y=10$$$, $$$a=2$$$, and $$$b=3$$$. At the $$$1$$$-st second, each rabbit will be at position $$$2$$$ and $$$7$$$. At the $$$2$$$-nd second, both rabbits will be at position $$$4$$$.

Gildong is now wondering: Will the two rabbits be at the same position at the same moment? If so, how long will it take? Let's find a moment in time (in seconds) after which the rabbits will be at the same point.

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

Each test case contains exactly one line. The line consists of four integers $$$x$$$, $$$y$$$, $$$a$$$, $$$b$$$ ($$$0 \le x \lt y \le 10^9$$$, $$$1 \le a,b \le 10^9$$$) — the current position of the taller rabbit, the current position of the shorter rabbit, the hopping distance of the taller rabbit, and the hopping distance of the shorter rabbit, respectively.

## Output Format
For each test case, print the single integer: number of seconds the two rabbits will take to be at the same position.

If the two rabbits will never be at the same position simultaneously, print $$$-1$$$.

## Examples
```input
5
0 10 2 3
0 10 3 3
900000000 1000000000 1 9999999
1 2 1 1
1 3 1 1
```
```output
2
-1
10
-1
1
```

## Note
The first case is explained in the description.

In the second case, each rabbit will be at position $$$3$$$ and $$$7$$$ respectively at the $$$1$$$-st second. But in the $$$2$$$-nd second they will be at $$$6$$$ and $$$4$$$ respectively, and we can see that they will never be at the same position since the distance between the two rabbits will only increase afterward.

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
Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse. For example, strings "pop", "noon", "x", and "kkkkkk" are palindromes, while strings "moon", "tv", and "abab" are not. An empty string is also a palindrome.

Gildong loves this concept so much, so he wants to play with it. He has $$$n$$$ distinct strings of equal length $$$m$$$. He wants to discard some of the strings (possibly none or all) and reorder the remaining strings so that the concatenation becomes a palindrome. He also wants the palindrome to be as long as possible. Please help him find one.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 50$$$) — the number of strings and the length of each string.

Next $$$n$$$ lines contain a string of length $$$m$$$ each, consisting of lowercase Latin letters only. All strings are distinct.

## Output Format
In the first line, print the length of the longest palindrome string you made.

In the second line, print that palindrome. If there are multiple answers, print any one of them. If the palindrome is empty, print an empty line or don't print this line at all.

## Examples
```input
3 3
tab
one
bat
```
```output
6
tabbat
```
-----
```input
4 2
oo
ox
xo
xx
```
```output
6
oxxxxo
```
-----
```input
3 5
hello
codef
orces
```
```output
0
```
-----
```input
9 4
abab
baba
abcd
bcde
cdef
defg
wxyz
zyxw
ijji
```
```output
20
ababwxyzijjizyxwbaba
```

## Note
In the first example, "battab" is also a valid answer.

In the second example, there can be 4 different valid answers including the sample output. We are not going to provide any hints for what the others are.

In the third example, the empty string is the only valid palindrome string.

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
The only difference between easy and hard versions is the constraint on $$$k$$$.

Gildong loves observing animals, so he bought two cameras to take videos of wild animals in a forest. The color of one camera is red, and the other one's color is blue.

Gildong is going to take videos for $$$n$$$ days, starting from day $$$1$$$ to day $$$n$$$. The forest can be divided into $$$m$$$ areas, numbered from $$$1$$$ to $$$m$$$. He'll use the cameras in the following way:

- On every odd day ($$$1$$$-st, $$$3$$$-rd, $$$5$$$-th, ...), bring the red camera to the forest and record a video for $$$2$$$ days.
- On every even day ($$$2$$$-nd, $$$4$$$-th, $$$6$$$-th, ...), bring the blue camera to the forest and record a video for $$$2$$$ days.
- If he starts recording on the $$$n$$$-th day with one of the cameras, the camera records for only one day.

Each camera can observe $$$k$$$ consecutive areas of the forest. For example, if $$$m=5$$$ and $$$k=3$$$, he can put a camera to observe one of these three ranges of areas for two days: $$$[1,3]$$$, $$$[2,4]$$$, and $$$[3,5]$$$.

Gildong got information about how many animals will be seen in each area each day. Since he would like to observe as many animals as possible, he wants you to find the best way to place the two cameras for $$$n$$$ days. Note that if the two cameras are observing the same area on the same day, the animals observed in that area are counted only once.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le m \le 2 \cdot 10^4$$$, $$$1 \le k \le min(m,20)$$$) – the number of days Gildong is going to record, the number of areas of the forest, and the range of the cameras, respectively.

Next $$$n$$$ lines contain $$$m$$$ integers each. The $$$j$$$-th integer in the $$$i+1$$$-st line is the number of animals that can be seen on the $$$i$$$-th day in the $$$j$$$-th area. Each number of animals is between $$$0$$$ and $$$1000$$$, inclusive.

## Output Format
Print one integer – the maximum number of animals that can be observed.

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

## Note
The optimal way to observe animals in the four examples are as follows:

Example 1:

Example 2:

Example 3:

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

# Problem
The only difference between easy and hard versions is the constraint on $$$k$$$.

Gildong loves observing animals, so he bought two cameras to take videos of wild animals in a forest. The color of one camera is red, and the other one's color is blue.

Gildong is going to take videos for $$$n$$$ days, starting from day $$$1$$$ to day $$$n$$$. The forest can be divided into $$$m$$$ areas, numbered from $$$1$$$ to $$$m$$$. He'll use the cameras in the following way:

- On every odd day ($$$1$$$-st, $$$3$$$-rd, $$$5$$$-th, ...), bring the red camera to the forest and record a video for $$$2$$$ days.
- On every even day ($$$2$$$-nd, $$$4$$$-th, $$$6$$$-th, ...), bring the blue camera to the forest and record a video for $$$2$$$ days.
- If he starts recording on the $$$n$$$-th day with one of the cameras, the camera records for only one day.

Each camera can observe $$$k$$$ consecutive areas of the forest. For example, if $$$m=5$$$ and $$$k=3$$$, he can put a camera to observe one of these three ranges of areas for two days: $$$[1,3]$$$, $$$[2,4]$$$, and $$$[3,5]$$$.

Gildong got information about how many animals will be seen in each area on each day. Since he would like to observe as many animals as possible, he wants you to find the best way to place the two cameras for $$$n$$$ days. Note that if the two cameras are observing the same area on the same day, the animals observed in that area are counted only once.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le m \le 2 \cdot 10^4$$$, $$$1 \le k \le m$$$) – the number of days Gildong is going to record, the number of areas of the forest, and the range of the cameras, respectively.

Next $$$n$$$ lines contain $$$m$$$ integers each. The $$$j$$$-th integer in the $$$i+1$$$-st line is the number of animals that can be seen on the $$$i$$$-th day in the $$$j$$$-th area. Each number of animals is between $$$0$$$ and $$$1000$$$, inclusive.

## Output Format
Print one integer – the maximum number of animals that can be observed.

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

## Note
The optimal way to observe animals in the four examples are as follows:

Example 1:

Example 2:

Example 3:

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

# Problem
Dreamoon likes strings. Today he created a game about strings:

String $$$s_1, s_2, \ldots, s_n$$$ is beautiful if and only if for each $$$1 \le i < n, s_i \ne s_{i+1}$$$.

Initially, Dreamoon has a string $$$a$$$. In each step Dreamoon can choose a beautiful substring of $$$a$$$ and remove it. Then he should concatenate the remaining characters (in the same order).

Dreamoon wants to use the smallest number of steps to make $$$a$$$ empty. Please help Dreamoon, and print any sequence of the smallest number of steps to make $$$a$$$ empty.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 200\,000$$$), denoting the number of test cases in the input.

For each test case, there's one line with a non-empty string of lowercase Latin letters $$$a$$$.

The total sum of lengths of strings in all test cases is at most $$$200\,000$$$.

## Output Format
For each test case, in the first line, you should print $$$m$$$: the smallest number of steps to make $$$a$$$ empty. Each of the following $$$m$$$ lines should contain two integers $$$l_i, r_i$$$ ($$$1 \leq l_i \leq r_i \leq |a|$$$), denoting, that the $$$i$$$-th step is removing the characters from index $$$l_i$$$ to $$$r_i$$$ in the current string. (indices are numbered starting from $$$1$$$).

Note that after the deletion of the substring, indices of remaining characters may change, and $$$r_i$$$ should be at most the current length of $$$a$$$.

If there are several possible solutions, you can print any.

## Examples
```input
4
aabbcc
aaabbb
aaa
abacad
```
```output
3
3 3
2 4
1 2
3
3 4
2 3
1 2
3
1 1
1 1
1 1
1
1 6
```

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

# Problem
There is a string of length $$$n+1$$$ of characters 'A' and 'B'. The first character and last character of the string are equal to 'A'.

You are given $$$m$$$ indices $$$p_1, p_2, \ldots, p_m$$$ ($$$0$$$-indexation) denoting the other indices of characters 'A' in the string.

Let's denote the minimum distance between two neighboring 'A' as $$$l$$$, and maximum distance between neighboring 'A' as $$$r$$$.

For example, $$$(l,r)$$$ of string "ABBAABBBA" is $$$(1,4)$$$.

And let's denote the balance degree of a string as the value of $$$r-l$$$.

Now Dreamoon wants to change exactly $$$k$$$ characters from 'B' to 'A', and he wants to make the balance degree of the string as small as possible.

Please calculate the required minimum possible value of balance degree.

## Input Format
The first line contains one integer $$$t$$$ denoting the number of test cases ($$$1 \leq t \leq 400\,000$$$).

For each test case, the first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{15}, 0 \leq m \leq 400\,000, 0 \leq k < n - m$$$).

The second line contains $$$m$$$ integers $$$p_1, p_2, \ldots, p_m$$$, ($$$0 < p_1 < p_2 < \ldots < p_m < n$$$).

The total sum of $$$m$$$ is at most $$$400\,000$$$.

## Output Format
For each test case, print one integer: the smallest possible value of balance degree after $$$k$$$ changes of 'B' to 'A'.

## Examples
```input
5
80 3 5
11 24 50
81 7 12
4 10 17 26 37 48 61
25 10 14
3 4 7 12 13 15 17 19 21 23
1 0 0

10 2 0
2 4
```
```output
5
2
0
0
4
```

Now solve the problem and return the code.