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

# Problem
Vasya has an array of integers of length n.

Vasya performs the following operations on the array: on each step he finds the longest segment of consecutive equal integers (the leftmost, if there are several such segments) and removes it. For example, if Vasya's array is [13, 13, 7, 7, 7, 2, 2, 2], then after one operation it becomes [13, 13, 2, 2, 2].

Compute the number of operations Vasya should make until the array becomes empty, i.e. Vasya removes all elements from it.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 200 000) — the length of the array.

The second line contains a sequence a1, a2, ..., an (1 ≤ ai ≤ 109) — Vasya's array.

## Output Format
Print the number of operations Vasya should make to remove all elements from the array.

## Examples
```input
4
2 5 5 2
```
```output
2
```
-----
```input
5
6 3 4 1 5
```
```output
5
```
-----
```input
8
4 4 4 2 2 100 100 100
```
```output
3
```
-----
```input
6
10 10 50 10 50 50
```
```output
4
```

## Note
In the first example, at first Vasya removes two fives at the second and third positions. The array becomes [2, 2]. In the second operation Vasya removes two twos at the first and second positions. After that the array becomes empty.

In the second example Vasya has to perform five operations to make the array empty. In each of them he removes the first element from the array.

In the third example Vasya needs three operations. In the first operation he removes all integers 4, in the second — all integers 100, in the third — all integers 2.

In the fourth example in the first operation Vasya removes the first two integers 10. After that the array becomes [50, 10, 50, 50]. Then in the second operation Vasya removes the two rightmost integers 50, so that the array becomes [50, 10]. In the third operation he removes the remaining 50, and the array becomes [10] after that. In the last, fourth operation he removes the only remaining 10. The array is empty after that.

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
Petya has a string of length n consisting of small and large English letters and digits.

He performs m operations. Each operation is described with two integers l and r and a character c: Petya removes from the string all characters c on positions between l and r, inclusive. It's obvious that the length of the string remains the same or decreases after each operation.

Find how the string will look like after Petya performs all m operations.

## Input Format
The first string contains two integers n and m (1 ≤ n, m ≤ 2·105) — the length of the string and the number of operations.

The second line contains the string of length n, consisting of small and large English letters and digits. Positions in the string are enumerated from 1.

Each of the next m lines contains two integers l and r (1 ≤ l ≤ r), followed by a character c, which is a small or large English letter or a digit. This line describes one operation. It is guaranteed that r doesn't exceed the length of the string s before current operation.

## Output Format
Print the string Petya will obtain after performing all m operations. If the strings becomes empty after all operations, print an empty line.

## Examples
```input
4 2
abac
1 3 a
2 2 c
```
```output
b
```
-----
```input
3 2
A0z
1 3 0
1 1 z
```
```output
Az
```
-----
```input
10 4
agtFrgF4aF
2 5 g
4 9 F
1 5 4
1 7 a
```
```output
tFrg4
```
-----
```input
9 5
aAAaBBccD
1 4 a
5 6 c
2 3 B
4 4 D
2 3 A
```
```output
AB
```

## Note
In the first example during the first operation both letters 'a' are removed, so the string becomes "bc". During the second operation the letter 'c' (on the second position) is removed, and the string becomes "b".

In the second example during the first operation Petya removes '0' from the second position. After that the string becomes "Az". During the second operations the string doesn't change.

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 frog lives on the axis Ox and needs to reach home which is in the point n. She starts from the point 1. The frog can jump to the right at a distance not more than d. So, after she jumped from the point x she can reach the point x + a, where a is an integer from 1 to d.

For each point from 1 to n is known if there is a lily flower in it. The frog can jump only in points with a lilies. Guaranteed that there are lilies in the points 1 and n.

Determine the minimal number of jumps that the frog needs to reach home which is in the point n from the point 1. Consider that initially the frog is in the point 1. If the frog can not reach home, print -1.

## Input Format
The first line contains two integers n and d (2 ≤ n ≤ 100, 1 ≤ d ≤ n - 1) — the point, which the frog wants to reach, and the maximal length of the frog jump.

The second line contains a string s of length n, consisting of zeros and ones. If a character of the string s equals to zero, then in the corresponding point there is no lily flower. In the other case, in the corresponding point there is a lily flower. Guaranteed that the first and the last characters of the string s equal to one.

## Output Format
If the frog can not reach the home, print -1.

In the other case, print the minimal number of jumps that the frog needs to reach the home which is in the point n from the point 1.

## Examples
```input
8 4
10010101
```
```output
2
```
-----
```input
4 2
1001
```
```output
-1
```
-----
```input
8 4
11100101
```
```output
3
```
-----
```input
12 3
101111100101
```
```output
4
```

## Note
In the first example the from can reach home in two jumps: the first jump from the point 1 to the point 4 (the length of the jump is three), and the second jump from the point 4 to the point 8 (the length of the jump is four).

In the second example the frog can not reach home, because to make it she need to jump on a distance three, but the maximum length of her jump equals to two.

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
Petya has equal wooden bars of length n. He wants to make a frame for two equal doors. Each frame has two vertical (left and right) sides of length a and one top side of length b. A solid (i.e. continuous without breaks) piece of bar is needed for each side.

Determine a minimal number of wooden bars which are needed to make the frames for two doors. Petya can cut the wooden bars into any parts, but each side of each door should be a solid piece of a wooden bar (or a whole wooden bar).

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 1 000) — the length of each wooden bar.

The second line contains a single integer a (1 ≤ a ≤ n) — the length of the vertical (left and right) sides of a door frame.

The third line contains a single integer b (1 ≤ b ≤ n) — the length of the upper side of a door frame.

## Output Format
Print the minimal number of wooden bars with length n which are needed to make the frames for two doors.

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

## Note
In the first example one wooden bar is enough, since the total length of all six sides of the frames for two doors is 8.

In the second example 6 wooden bars is enough, because for each side of the frames the new wooden bar is needed.

Now solve the problem and return the code.