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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.5 seconds
Memory limit: 256.0 MB

# Problem
Vanya is in the palace that can be represented as a grid n × m. Each room contains a single chest, an the room located in the i-th row and j-th columns contains the chest of type aij. Each chest of type x ≤ p - 1 contains a key that can open any chest of type x + 1, and all chests of type 1 are not locked. There is exactly one chest of type p and it contains a treasure.

Vanya starts in cell (1, 1) (top left corner). What is the minimum total distance Vanya has to walk in order to get the treasure? Consider the distance between cell (r1, c1) (the cell in the row r1 and column c1) and (r2, c2) is equal to |r1 - r2| + |c1 - c2|.

## Input Format
The first line of the input contains three integers n, m and p (1 ≤ n, m ≤ 300, 1 ≤ p ≤ n·m) — the number of rows and columns in the table representing the palace and the number of different types of the chests, respectively.

Each of the following n lines contains m integers aij (1 ≤ aij ≤ p) — the types of the chests in corresponding rooms. It's guaranteed that for each x from 1 to p there is at least one chest of this type (that is, there exists a pair of r and c, such that arc = x). Also, it's guaranteed that there is exactly one chest of type p.

## Output Format
Print one integer — the minimum possible total distance Vanya has to walk in order to get the treasure from the chest of type p.

## Examples
```input
3 4 3
2 1 1 1
1 1 1 1
2 1 1 3
```
```output
5
```
-----
```input
3 3 9
1 3 5
8 9 7
4 6 2
```
```output
22
```
-----
```input
3 4 12
1 2 3 4
8 7 6 5
9 10 11 12
```
```output
11
```

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Vanya plays a game of balloons on the field of size n × n, where each cell contains a balloon with one of the values 0, 1, 2 or 3. The goal is to destroy a cross, such that the product of all values of balloons in the cross is maximum possible. There are two types of crosses: normal and rotated. For example:

or

Formally, the cross is given by three integers r, c and d, such that d ≤ r, c ≤ n - d + 1. The normal cross consists of balloons located in cells (x, y) (where x stay for the number of the row and y for the number of the column), such that |x - r|·|y - c| = 0 and |x - r| + |y - c| < d. Rotated cross consists of balloons located in cells (x, y), such that |x - r| = |y - c| and |x - r| < d.

Vanya wants to know the maximum possible product of the values of balls forming one cross. As this value can be large, output it modulo 109 + 7.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of rows and columns in the table with balloons.

The each of the following n lines contains n characters '0', '1', '2' or '3' — the description of the values in balloons.

## Output Format
Print the maximum possible product modulo 109 + 7. Note, that you are not asked to maximize the remainder modulo 109 + 7, but to find the maximum value and print it this modulo.

## Examples
```input
4
1233
0213
2020
0303
```
```output
108
```
-----
```input
5
00300
00300
33333
00300
00300
```
```output
19683
```
-----
```input
5
00003
02030
00300
03020
30000
```
```output
108
```
-----
```input
5
21312
10003
10002
10003
23231
```
```output
3
```
-----
```input
5
12131
12111
12112
21311
21212
```
```output
24
```

## Note
In the first sample, the maximum product is achieved for a rotated cross with a center in the cell (3, 3) and radius 1: 2·2·3·3·3 = 108.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
After their adventure with the magic mirror Kay and Gerda have returned home and sometimes give free ice cream to kids in the summer.

At the start of the day they have x ice cream packs. Since the ice cream is free, people start standing in the queue before Kay and Gerda's house even in the night. Each person in the queue wants either to take several ice cream packs for himself and his friends or to give several ice cream packs to Kay and Gerda (carriers that bring ice cream have to stand in the same queue).

If a carrier with d ice cream packs comes to the house, then Kay and Gerda take all his packs. If a child who wants to take d ice cream packs comes to the house, then Kay and Gerda will give him d packs if they have enough ice cream, otherwise the child will get no ice cream at all and will leave in distress.

Kay wants to find the amount of ice cream they will have after all people will leave from the queue, and Gerda wants to find the number of distressed kids.

## Input Format
The first line contains two space-separated integers n and x (1 ≤ n ≤ 1000, 0 ≤ x ≤ 109).

Each of the next n lines contains a character '+' or '-', and an integer di, separated by a space (1 ≤ di ≤ 109). Record "+ di" in i-th line means that a carrier with di ice cream packs occupies i-th place from the start of the queue, and record "- di" means that a child who wants to take di packs stands in i-th place.

## Output Format
Print two space-separated integers — number of ice cream packs left after all operations, and number of kids that left the house in distress.

## Examples
```input
5 7
+ 5
- 10
- 20
+ 40
- 20
```
```output
22 1
```
-----
```input
5 17
- 16
- 2
- 98
+ 100
- 98
```
```output
3 2
```

## Note
Consider the first sample.

1. Initially Kay and Gerda have 7 packs of ice cream.
2. Carrier brings 5 more, so now they have 12 packs.
3. A kid asks for 10 packs and receives them. There are only 2 packs remaining.
4. Another kid asks for 20 packs. Kay and Gerda do not have them, so the kid goes away distressed.
5. Carrier bring 40 packs, now Kay and Gerda have 42 packs.
6. Kid asks for 20 packs and receives them. There are 22 packs remaining.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Little Robber Girl likes to scare animals in her zoo for fun. She decided to arrange the animals in a row in the order of non-decreasing height. However, the animals were so scared that they couldn't stay in the right places.

The robber girl was angry at first, but then she decided to arrange the animals herself. She repeatedly names numbers l and r such that r - l + 1 is even. After that animals that occupy positions between l and r inclusively are rearranged as follows: the animal at position l swaps places with the animal at position l + 1, the animal l + 2 swaps with the animal l + 3, ..., finally, the animal at position r - 1 swaps with the animal r.

Help the robber girl to arrange the animals in the order of non-decreasing height. You should name at most 20 000 segments, since otherwise the robber girl will become bored and will start scaring the animals again.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 100) — number of animals in the robber girl's zoo.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the height of the animal occupying the i-th place.

## Output Format
Print the sequence of operations that will rearrange the animals by non-decreasing height.

The output should contain several lines, i-th of the lines should contain two space-separated integers li and ri (1 ≤ li < ri ≤ n) — descriptions of segments the robber girl should name. The segments should be described in the order the operations are performed.

The number of operations should not exceed 20 000.

If the animals are arranged correctly from the start, you are allowed to output nothing.

## Examples
```input
4
2 1 4 3
```
```output
1 4
```
-----
```input
7
36 28 57 39 66 69 68
```
```output
1 4
6 7
```
-----
```input
5
1 2 1 2 1
```
```output
2 5
3 4
1 4
1 4
```

## Note
Note that you don't have to minimize the number of operations. Any solution that performs at most 20 000 operations is allowed.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.5 seconds
Memory limit: 256.0 MB

# Problem
Owl Sonya decided to become a partymaker. To train for this role she gather all her owl friends in the country house. There are m chairs located in a circle and consequently numbered with integers from 1 to m. Thus, chairs i and i + 1 are neighbouring for all i from 1 to m - 1. Chairs 1 and m are also neighbouring. Some chairs are occupied by her friends. There are n friends in total. No two friends occupy the same chair. Rules are the following:

1. Each participant removes from the game the chair he is currently sitting on.
2. Each of the participants choose a direction that she will follow: clockwise (indices increase, from m goes to 1) and counter-clockwise (indices decrease, from 1 goes to m). This direction may coincide or be different for any pair of owls.
3. Each turn all guests move one step in the chosen directions. If some guest move to the position with a chair there, he removes this chair from the game.
4. Game ends if there are no more chairs left in the game.

Owls are very busy and want to get rid of the game as soon as possible. They cooperate to pick the direction. Your goal is to find the minimum number o moves required to finish the game.

## Input Format
The first line of the input contains a single integer m (1 ≤ m ≤ 109) — the length of the circle.

The second line contains a single integer n (1 ≤ n ≤ 100 000) — the number of friends.

Last line contains an increasing sequence of n integers ai (1 ≤ ai ≤ m) — initial positions of all owls.

## Output Format
Print the minimum number of move required to finish the game. Note, that 0 also may be an answer.

## Examples
```input
6
3
1 3 5
```
```output
1
```
-----
```input
6
2
1 6
```
```output
2
```
-----
```input
406
6
1 2 3 204 205 206
```
```output
100
```

## Note
In the first sample, it's possible if all owls will move clockwise, i.e. in the direction of increasing indices.

In the sample, first owl has to move clockwise, while the second — counterclockwise.

In the third sample, the first and the fourth owls should move counterclockwise, while the third and the sixth — clockwise. The second and the firth may move in any direction.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The Prodiggers are quite a cool band and for this reason, they have been the surprise guest at the ENTER festival for the past 80 years. At the beginning of their careers, they weren’t so successful, so they had to spend time digging channels to earn money; hence the name. Anyway, they like to tour a lot and have surprising amounts of energy to do extremely long tours. However, they hate spending two consecutive days without having a concert, so they would like to avoid it.

A tour is defined by a sequence of concerts and days-off. You need to count in how many ways The Prodiggers can select k different tours of the same length between l and r.

For example if k = 2, l = 1 and r = 2, if we define concert day as {1} and day-off as {0}, here are all possible tours: {0}, {1}, {00}, {01}, {10}, {11}. But tour 00 can not be selected because it has 2 days-off in a row. Now, we need to count in how many ways we can select k = 2 tours of the same length in range [1;2]. Here they are: {0,1}; {01,10}; {01,11}; {10,11}.

Since their schedule is quite busy, they want you to tell them in how many ways can do that, modulo 1 000 000 007 (109 + 7).

## Input Format
The first line of the input contains three integers k, l and r (1 ≤ k ≤ 200, 1 ≤ l ≤ r ≤ 1018).

## Output Format
Output a single number: the number of ways to select k different tours of the same length, modulo 1 000 000 007.

## Examples
```input
1 1 2
```
```output
5
```

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
R3D3 spent some time on an internship in MDCS. After earning enough money, he decided to go on a holiday somewhere far, far away. He enjoyed suntanning, drinking alcohol-free cocktails and going to concerts of popular local bands. While listening to "The White Buttons" and their hit song "Dacan the Baker", he met another robot for whom he was sure is the love of his life. Well, his summer, at least. Anyway, R3D3 was too shy to approach his potential soulmate, so he decided to write her a love letter. However, he stumbled upon a problem. Due to a terrorist threat, the Intergalactic Space Police was monitoring all letters sent in the area. Thus, R3D3 decided to invent his own alphabet, for which he was sure his love would be able to decipher.

There are n letters in R3D3’s alphabet, and he wants to represent each letter as a sequence of '0' and '1', so that no letter’s sequence is a prefix of another letter's sequence. Since the Intergalactic Space Communications Service has lately introduced a tax for invented alphabets, R3D3 must pay a certain amount of money for each bit in his alphabet’s code (check the sample test for clarifications). He is too lovestruck to think clearly, so he asked you for help.

Given the costs c0 and c1 for each '0' and '1' in R3D3’s alphabet, respectively, you should come up with a coding for the alphabet (with properties as above) with minimum total cost.

## Input Format
The first line of input contains three integers n (2 ≤ n ≤ 108), c0 and c1 (0 ≤ c0, c1 ≤ 108) — the number of letters in the alphabet, and costs of '0' and '1', respectively.

## Output Format
Output a single integer — minimum possible total a cost of the whole alphabet.

## Examples
```input
4 1 2
```
```output
12
```

## Note
There are 4 letters in the alphabet. The optimal encoding is "00", "01", "10", "11". There are 4 zeroes and 4 ones used, so the total cost is 4·1 + 4·2 = 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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a broken clock. You know, that it is supposed to show time in 12- or 24-hours HH:MM format. In 12-hours format hours change from 1 to 12, while in 24-hours it changes from 0 to 23. In both formats minutes change from 0 to 59.

You are given a time in format HH:MM that is currently displayed on the broken clock. Your goal is to change minimum number of digits in order to make clocks display the correct time in the given format.

For example, if 00:99 is displayed, it is enough to replace the second 9 with 3 in order to get 00:39 that is a correct time in 24-hours format. However, to make 00:99 correct in 12-hours format, one has to change at least two digits. Additionally to the first change one can replace the second 0 with 1 and obtain 01:39.

## Input Format
The first line of the input contains one integer 12 or 24, that denote 12-hours or 24-hours format respectively.

The second line contains the time in format HH:MM, that is currently displayed on the clock. First two characters stand for the hours, while next two show the minutes.

## Output Format
The only line of the output should contain the time in format HH:MM that is a correct time in the given format. It should differ from the original in as few positions as possible. If there are many optimal solutions you can print any of them.

## Examples
```input
24
17:30
```
```output
17:30
```
-----
```input
12
17:30
```
```output
07:30
```
-----
```input
24
99:99
```
```output
09:09
```

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a text consisting of n lines. Each line contains some space-separated words, consisting of lowercase English letters.

We define a syllable as a string that contains exactly one vowel and any arbitrary number (possibly none) of consonants. In English alphabet following letters are considered to be vowels: 'a', 'e', 'i', 'o', 'u' and 'y'.

Each word of the text that contains at least one vowel can be divided into syllables. Each character should be a part of exactly one syllable. For example, the word "mamma" can be divided into syllables as "ma" and "mma", "mam" and "ma", and "mamm" and "a". Words that consist of only consonants should be ignored.

The verse patterns for the given text is a sequence of n integers p1, p2, ..., pn. Text matches the given verse pattern if for each i from 1 to n one can divide words of the i-th line in syllables in such a way that the total number of syllables is equal to pi.

You are given the text and the verse pattern. Check, if the given text matches the given verse pattern.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 100) — the number of lines in the text.

The second line contains integers p1, ..., pn (0 ≤ pi ≤ 100) — the verse pattern.

Next n lines contain the text itself. Text consists of lowercase English letters and spaces. It's guaranteed that all lines are non-empty, each line starts and ends with a letter and words are separated by exactly one space. The length of each line doesn't exceed 100 characters.

## Output Format
If the given text matches the given verse pattern, then print "YES" (without quotes) in the only line of the output. Otherwise, print "NO" (without quotes).

## Examples
```input
3
2 2 3
intel
code
ch allenge
```
```output
YES
```
-----
```input
4
1 2 3 1
a
bcdefghi
jklmnopqrstu
vwxyz
```
```output
NO
```
-----
```input
4
13 11 15 15
to be or not to be that is the question
whether tis nobler in the mind to suffer
the slings and arrows of outrageous fortune
or to take arms against a sea of troubles
```
```output
YES
```

## Note
In the first sample, one can split words into syllables in the following way:

Since the word "ch" in the third line doesn't contain vowels, we can ignore it. As the result we get 2 syllabels in first two lines and 3 syllables in the third one.

Now solve the problem and return the code.