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

# Problem
Methodius received an email from his friend Polycarp. However, Polycarp's keyboard is broken, so pressing a key on it once may cause the corresponding symbol to appear more than once (if you press a key on a regular keyboard, it prints exactly one symbol).

For example, as a result of typing the word "hello", the following words could be printed: "hello", "hhhhello", "hheeeellllooo", but the following could not be printed: "hell", "helo", "hhllllooo".

Note, that when you press a key, the corresponding symbol must appear (possibly, more than once). The keyboard is broken in a random manner, it means that pressing the same key you can get the different number of letters in the result.

For each word in the letter, Methodius has guessed what word Polycarp actually wanted to write, but he is not sure about it, so he asks you to help him.

You are given a list of pairs of words. For each pair, determine if the second word could be printed by typing the first one on Polycarp's keyboard.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of pairs to check. Further input contains $$$n$$$ descriptions of pairs.

The first line of each description contains a single non-empty word $$$s$$$ consisting of lowercase Latin letters. The second line of the description contains a single non-empty word $$$t$$$ consisting of lowercase Latin letters. The lengths of both strings are not greater than $$$10^6$$$.

It is guaranteed that the total length of all words $$$s$$$ in the input is not greater than $$$10^6$$$. Also, it is guaranteed that the total length of all words $$$t$$$ in the input is not greater than $$$10^6$$$.

## Output Format
Output $$$n$$$ lines. In the $$$i$$$-th line for the $$$i$$$-th pair of words $$$s$$$ and $$$t$$$ print YES if the word $$$t$$$ could be printed by typing the word $$$s$$$. Otherwise, print NO.

## Examples
```input
4
hello
hello
hello
helloo
hello
hlllloo
hello
helo
```
```output
YES
YES
NO
NO
```
-----
```input
5
aa
bb
codeforces
codeforce
polycarp
poolycarpp
aaaa
aaaab
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxyz
```
```output
NO
NO
YES
NO
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A sequence $$$a_1, a_2, \dots, a_k$$$ is called an arithmetic progression if for each $$$i$$$ from $$$1$$$ to $$$k$$$ elements satisfy the condition $$$a_i = a_1 + c \cdot (i - 1)$$$ for some fixed $$$c$$$.

For example, these five sequences are arithmetic progressions: $$$[5, 7, 9, 11]$$$, $$$[101]$$$, $$$[101, 100, 99]$$$, $$$[13, 97]$$$ and $$$[5, 5, 5, 5, 5]$$$. And these four sequences aren't arithmetic progressions: $$$[3, 1, 2]$$$, $$$[1, 2, 4, 8]$$$, $$$[1, -1, 1, -1]$$$ and $$$[1, 2, 3, 3, 3]$$$.

You are given a sequence of integers $$$b_1, b_2, \dots, b_n$$$. Find any index $$$j$$$ ($$$1 \le j \le n$$$), such that if you delete $$$b_j$$$ from the sequence, you can reorder the remaining $$$n-1$$$ elements, so that you will get an arithmetic progression. If there is no such index, output the number -1.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — length of the sequence $$$b$$$. The second line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — elements of the sequence $$$b$$$.

## Output Format
Print such index $$$j$$$ ($$$1 \le j \le n$$$), so that if you delete the $$$j$$$-th element from the sequence, you can reorder the remaining elements, so that you will get an arithmetic progression. If there are multiple solutions, you are allowed to print any of them. If there is no such index, print -1.

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

## Note
Note to the first example. If you delete the $$$4$$$-th element, you can get the arithmetic progression $$$[2, 4, 6, 8]$$$.

Note to the second example. The original sequence is already arithmetic progression, so you can delete $$$1$$$-st or last element and you will get an arithmetical progression again.

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
For years, the Day of city N was held in the most rainy day of summer. New mayor decided to break this tradition and select a not-so-rainy day for the celebration. The mayor knows the weather forecast for the $$$n$$$ days of summer. On the $$$i$$$-th day, $$$a_i$$$ millimeters of rain will fall. All values $$$a_i$$$ are distinct.

The mayor knows that citizens will watch the weather $$$x$$$ days before the celebration and $$$y$$$ days after. Because of that, he says that a day $$$d$$$ is not-so-rainy if $$$a_d$$$ is smaller than rain amounts at each of $$$x$$$ days before day $$$d$$$ and and each of $$$y$$$ days after day $$$d$$$. In other words, $$$a_d < a_j$$$ should hold for all $$$d - x \le j < d$$$ and $$$d < j \le d + y$$$. Citizens only watch the weather during summer, so we only consider such $$$j$$$ that $$$1 \le j \le n$$$.

Help mayor find the earliest not-so-rainy day of summer.

## Input Format
The first line contains three integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le x, y \le 7$$$) — the number of days in summer, the number of days citizens watch the weather before the celebration and the number of days they do that after.

The second line contains $$$n$$$ distinct integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ denotes the rain amount on the $$$i$$$-th day.

## Output Format
Print a single integer — the index of the earliest not-so-rainy day of summer. We can show that the answer always exists.

## Examples
```input
10 2 2
10 9 6 7 8 3 2 1 4 5
```
```output
3
```
-----
```input
10 2 3
10 9 6 7 8 3 2 1 4 5
```
```output
8
```
-----
```input
5 5 5
100000 10000 1000 100 10
```
```output
5
```

## Note
In the first example days $$$3$$$ and $$$8$$$ are not-so-rainy. The $$$3$$$-rd day is earlier.

In the second example day $$$3$$$ is not not-so-rainy, because $$$3 + y = 6$$$ and $$$a_3 > a_6$$$. Thus, day $$$8$$$ is the answer. Note that $$$8 + y = 11$$$, but we don't consider day $$$11$$$, because it is not summer.

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
While sailing on a boat, Inessa noticed a beautiful water lily flower above the lake's surface. She came closer and it turned out that the lily was exactly $$$H$$$ centimeters above the water surface. Inessa grabbed the flower and sailed the distance of $$$L$$$ centimeters. Exactly at this point the flower touched the water surface.

Suppose that the lily grows at some point $$$A$$$ on the lake bottom, and its stem is always a straight segment with one endpoint at point $$$A$$$. Also suppose that initially the flower was exactly above the point $$$A$$$, i.e. its stem was vertical. Can you determine the depth of the lake at point $$$A$$$?

## Input Format
The only line contains two integers $$$H$$$ and $$$L$$$ ($$$1 \le H < L \le 10^{6}$$$).

## Output Format
Print a single number — the depth of the lake at point $$$A$$$. The absolute or relative error should 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
1 2
```
```output
1.5000000000000
```
-----
```input
3 5
```
```output
2.6666666666667
```

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
Amugae is in a very large round corridor. The corridor consists of two areas. The inner area is equally divided by $$$n$$$ sectors, and the outer area is equally divided by $$$m$$$ sectors. A wall exists between each pair of sectors of same area (inner or outer), but there is no wall between the inner area and the outer area. A wall always exists at the 12 o'clock position.

The inner area's sectors are denoted as $$$(1,1), (1,2), \dots, (1,n)$$$ in clockwise direction. The outer area's sectors are denoted as $$$(2,1), (2,2), \dots, (2,m)$$$ in the same manner. For a clear understanding, see the example image above.

Amugae wants to know if he can move from one sector to another sector. He has $$$q$$$ questions.

For each question, check if he can move between two given sectors.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 10^{18}$$$, $$$1 \le q \le 10^4$$$) — the number of sectors in the inner area, the number of sectors in the outer area and the number of questions.

Each of the next $$$q$$$ lines contains four integers $$$s_x$$$, $$$s_y$$$, $$$e_x$$$, $$$e_y$$$ ($$$1 \le s_x, e_x \le 2$$$; if $$$s_x = 1$$$, then $$$1 \le s_y \le n$$$, otherwise $$$1 \le s_y \le m$$$; constraints on $$$e_y$$$ are similar). Amague wants to know if it is possible to move from sector $$$(s_x, s_y)$$$ to sector $$$(e_x, e_y)$$$.

## Output Format
For each question, print "YES" if Amugae can move from $$$(s_x, s_y)$$$ to $$$(e_x, e_y)$$$, and "NO" otherwise.

You can print each letter in any case (upper or lower).

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

## Note
Example is shown on the picture in the statement.

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

# Problem
Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is square-shaped consisting of $$$n$$$ rows and $$$n$$$ columns of square cells. The rows are numbered from $$$1$$$ to $$$n$$$, from top to bottom, and the columns are numbered from $$$1$$$ to $$$n$$$, from left to right. The position of a cell at row $$$r$$$ and column $$$c$$$ is represented as $$$(r, c)$$$. There are only two colors for the cells in cfpaint — black and white.

There is a tool named eraser in cfpaint. The eraser has an integer size $$$k$$$ ($$$1 \le k \le n$$$). To use the eraser, Gildong needs to click on a cell $$$(i, j)$$$ where $$$1 \le i, j \le n - k + 1$$$. When a cell $$$(i, j)$$$ is clicked, all of the cells $$$(i', j')$$$ where $$$i \le i' \le i + k - 1$$$ and $$$j \le j' \le j + k - 1$$$ become white. In other words, a square with side equal to $$$k$$$ cells and top left corner at $$$(i, j)$$$ is colored white.

A white line is a row or a column without any black cells.

Gildong has worked with cfpaint for some time, so some of the cells (possibly zero or all) are currently black. He wants to know the maximum number of white lines after using the eraser exactly once. Help Gildong find the answer to his question.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2000$$$) — the number of rows and columns, and the size of the eraser.

The next $$$n$$$ lines contain $$$n$$$ characters each without spaces. The $$$j$$$-th character in the $$$i$$$-th line represents the cell at $$$(i,j)$$$. Each character is given as either 'B' representing a black cell, or 'W' representing a white cell.

## Output Format
Print one integer: the maximum number of white lines after using the eraser exactly once.

## Examples
```input
4 2
BWWW
WBBW
WBBW
WWWB
```
```output
4
```
-----
```input
3 1
BWB
WWB
BWB
```
```output
2
```
-----
```input
5 3
BWBBB
BWBBB
BBBBB
BBBBB
WBBBW
```
```output
2
```
-----
```input
2 2
BW
WB
```
```output
4
```
-----
```input
2 1
WW
WW
```
```output
4
```

## Note
In the first example, Gildong can click the cell $$$(2, 2)$$$, then the working screen becomes:

Then there are four white lines — the $$$2$$$-nd and $$$3$$$-rd row, and the $$$2$$$-nd and $$$3$$$-rd column.

In the second example, clicking the cell $$$(2, 3)$$$ makes the $$$2$$$-nd row a white line.

In the third example, both the $$$2$$$-nd column and $$$5$$$-th row become white lines by clicking the cell $$$(3, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Amugae has a sentence consisting of $$$n$$$ words. He want to compress this sentence into one word. Amugae doesn't like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges "sample" and "please" into "samplease".

Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of the words in Amugae's sentence.

The second line contains $$$n$$$ words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits ('A', 'B', ..., 'Z', 'a', 'b', ..., 'z', '0', '1', ..., '9'). The total length of the words does not exceed $$$10^6$$$.

## Output Format
In the only line output the compressed word after the merging process ends as described in the problem.

## Examples
```input
5
I want to order pizza
```
```output
Iwantorderpizza
```
-----
```input
5
sample please ease in out
```
```output
sampleaseinout
```

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
In the city of Saint Petersburg, a day lasts for $$$2^{100}$$$ minutes. From the main station of Saint Petersburg, a train departs after $$$1$$$ minute, $$$4$$$ minutes, $$$16$$$ minutes, and so on; in other words, the train departs at time $$$4^k$$$ for each integer $$$k \geq 0$$$. Team BowWow has arrived at the station at the time $$$s$$$ and it is trying to count how many trains have they missed; in other words, the number of trains that have departed strictly before time $$$s$$$. For example if $$$s = 20$$$, then they missed trains which have departed at $$$1$$$, $$$4$$$ and $$$16$$$. As you are the only one who knows the time, help them!

Note that the number $$$s$$$ will be given you in a binary representation without leading zeroes.

## Input Format
The first line contains a single binary number $$$s$$$ ($$$0 \leq s < 2^{100}$$$) without leading zeroes.

## Output Format
Output a single number — the number of trains which have departed strictly before the time $$$s$$$.

## Examples
```input
100000000
```
```output
4
```
-----
```input
101
```
```output
2
```
-----
```input
10100
```
```output
3
```

## Note
In the first example $$$100000000_2 = 256_{10}$$$, missed trains have departed at $$$1$$$, $$$4$$$, $$$16$$$ and $$$64$$$.

In the second example $$$101_2 = 5_{10}$$$, trains have departed at $$$1$$$ and $$$4$$$.

The third example is explained in the statements.

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
Mislove had an array $$$a_1$$$, $$$a_2$$$, $$$\cdots$$$, $$$a_n$$$ of $$$n$$$ positive integers, but he has lost it. He only remembers the following facts about it:

- The number of different numbers in the array is not less than $$$l$$$ and is not greater than $$$r$$$;
- For each array's element $$$a_i$$$ either $$$a_i = 1$$$ or $$$a_i$$$ is even and there is a number $$$\dfrac{a_i}{2}$$$ in the array.

For example, if $$$n=5$$$, $$$l=2$$$, $$$r=3$$$ then an array could be $$$[1,2,2,4,4]$$$ or $$$[1,1,1,1,2]$$$; but it couldn't be $$$[1,2,2,4,8]$$$ because this array contains $$$4$$$ different numbers; it couldn't be $$$[1,2,2,3,3]$$$ because $$$3$$$ is odd and isn't equal to $$$1$$$; and it couldn't be $$$[1,1,2,2,16]$$$ because there is a number $$$16$$$ in the array but there isn't a number $$$\frac{16}{2} = 8$$$.

According to these facts, he is asking you to count the minimal and the maximal possible sums of all elements in an array.

## Input Format
The only input line contains three integers $$$n$$$, $$$l$$$ and $$$r$$$ ($$$1 \leq n \leq 1\,000$$$, $$$1 \leq l \leq r \leq \min(n, 20)$$$) — an array's size, the minimal number and the maximal number of distinct elements in an array.

## Output Format
Output two numbers — the minimal and the maximal possible sums of all elements in an array.

## Examples
```input
4 2 2
```
```output
5 7
```
-----
```input
5 1 5
```
```output
5 31
```

## Note
In the first example, an array could be the one of the following: $$$[1,1,1,2]$$$, $$$[1,1,2,2]$$$ or $$$[1,2,2,2]$$$. In the first case the minimal sum is reached and in the last case the maximal sum is reached.

In the second example, the minimal sum is reached at the array $$$[1,1,1,1,1]$$$, and the maximal one is reached at the array $$$[1,2,4,8,16]$$$.

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 only difference between easy and hard versions is the length of the string. You can hack this problem only if you solve both problems.

Kirk has a binary string $$$s$$$ (a string which consists of zeroes and ones) of length $$$n$$$ and he is asking you to find a binary string $$$t$$$ of the same length which satisfies the following conditions:

- For any $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) the length of the longest non-decreasing subsequence of the substring $$$s_{l}s_{l+1} \ldots s_{r}$$$ is equal to the length of the longest non-decreasing subsequence of the substring $$$t_{l}t_{l+1} \ldots t_{r}$$$;
- The number of zeroes in $$$t$$$ is the maximum possible.

A non-decreasing subsequence of a string $$$p$$$ is a sequence of indices $$$i_1, i_2, \ldots, i_k$$$ such that $$$i_1 < i_2 < \ldots < i_k$$$ and $$$p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$$$. The length of the subsequence is $$$k$$$.

If there are multiple substrings which satisfy the conditions, output any.

## Input Format
The first line contains a binary string of length not more than $$$2\: 000$$$.

## Output Format
Output a binary string which satisfied the above conditions. If there are many such strings, output any of them.

## Examples
```input
110
```
```output
010
```
-----
```input
010
```
```output
010
```
-----
```input
0001111
```
```output
0000000
```
-----
```input
0111001100111011101000
```
```output
0011001100001011101000
```

## Note
In the first example:

- For the substrings of the length $$$1$$$ the length of the longest non-decreasing subsequnce is $$$1$$$;
- For $$$l = 1, r = 2$$$ the longest non-decreasing subsequnce of the substring $$$s_{1}s_{2}$$$ is $$$11$$$ and the longest non-decreasing subsequnce of the substring $$$t_{1}t_{2}$$$ is $$$01$$$;
- For $$$l = 1, r = 3$$$ the longest non-decreasing subsequnce of the substring $$$s_{1}s_{3}$$$ is $$$11$$$ and the longest non-decreasing subsequnce of the substring $$$t_{1}t_{3}$$$ is $$$00$$$;
- For $$$l = 2, r = 3$$$ the longest non-decreasing subsequnce of the substring $$$s_{2}s_{3}$$$ is $$$1$$$ and the longest non-decreasing subsequnce of the substring $$$t_{2}t_{3}$$$ is $$$1$$$;

The second example is similar to the first one.

Now solve the problem and return the code.