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 collects coins: he has exactly one coin for every year from 1 to n. Naturally, Vasya keeps all the coins in his collection in the order in which they were released. Once Vasya's younger brother made a change — he took all the coins whose release year dated from l to r inclusively and put them in the reverse order. That is, he took a certain segment [l, r] and reversed it. At that the segment's endpoints did not coincide. For example, if n = 8, then initially Vasya's coins were kept in the order 1 2 3 4 5 6 7 8. If Vasya's younger brother chose the segment [2, 6], then after the reversal the coin order will change to 1 6 5 4 3 2 7 8. Vasya suspects that someone else could have spoilt the permutation after his brother. Help him to find that out. Check if the given permutation can be obtained from the permutation 1 2 ... n using exactly one segment reversal. If it is possible, find the segment itself.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 1000) which is the number of coins in Vasya's collection. The second line contains space-separated n integers which are the spoilt sequence of coins. It is guaranteed that the given sequence is a permutation, i.e. it contains only integers from 1 to n, and every number is used exactly 1 time.

## Output Format
If it is impossible to obtain the given permutation from the original one in exactly one action, print 0 0. Otherwise, print two numbers l r (1 ≤ l < r ≤ n) which are the endpoints of the segment that needs to be reversed to obtain from permutation 1 2 ... n the given one.

## Examples
```input
8
1 6 5 4 3 2 7 8
```
```output
2 6
```
-----
```input
4
2 3 4 1
```
```output
0 0
```
-----
```input
4
1 2 3 4
```
```output
0 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The Beroil corporation structure is hierarchical, that is it can be represented as a tree. Let's examine the presentation of this structure as follows:

- employee ::= name. | name:employee1,employee2, ... ,employeek.
- name ::= name of an employee

That is, the description of each employee consists of his name, a colon (:), the descriptions of all his subordinates separated by commas, and, finally, a dot. If an employee has no subordinates, then the colon is not present in his description.

For example, line MIKE:MAX.,ARTEM:MIKE..,DMITRY:DMITRY.,DMITRY... is the correct way of recording the structure of a corporation where the director MIKE has subordinates MAX, ARTEM and DMITRY. ARTEM has a subordinate whose name is MIKE, just as the name of his boss and two subordinates of DMITRY are called DMITRY, just like himself.

In the Beroil corporation every employee can only correspond with his subordinates, at that the subordinates are not necessarily direct. Let's call an uncomfortable situation the situation when a person whose name is s writes a letter to another person whose name is also s. In the example given above are two such pairs: a pair involving MIKE, and two pairs for DMITRY (a pair for each of his subordinates).

Your task is by the given structure of the corporation to find the number of uncomfortable pairs in it.

## Input Format
The first and single line contains the corporation structure which is a string of length from 1 to 1000 characters. It is guaranteed that the description is correct. Every name is a string consisting of capital Latin letters from 1 to 10 symbols in length.

## Output Format
Print a single number — the number of uncomfortable situations in the company.

## Examples
```input
MIKE:MAX.,ARTEM:MIKE..,DMITRY:DMITRY.,DMITRY...
```
```output
3
```
-----
```input
A:A..
```
```output
1
```
-----
```input
A:C:C:C:C.....
```
```output
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.0 seconds
Memory limit: 256.0 MB

# Problem
A top-secret military base under the command of Colonel Zuev is expecting an inspection from the Ministry of Defence. According to the charter, each top-secret military base must include a top-secret troop that should... well, we cannot tell you exactly what it should do, it is a top secret troop at the end. The problem is that Zuev's base is missing this top-secret troop for some reasons.

The colonel decided to deal with the problem immediately and ordered to line up in a single line all n soldiers of the base entrusted to him. Zuev knows that the loquacity of the i-th soldier from the left is equal to qi. Zuev wants to form the top-secret troop using k leftmost soldiers in the line, thus he wants their total loquacity to be as small as possible (as the troop should remain top-secret). To achieve this, he is going to choose a pair of consecutive soldiers and swap them. He intends to do so no more than s times. Note that any soldier can be a participant of such swaps for any number of times. The problem turned out to be unusual, and colonel Zuev asked you to help.

Determine, what is the minimum total loquacity of the first k soldiers in the line, that can be achieved by performing no more than s swaps of two consecutive soldiers.

## Input Format
The first line of the input contains three positive integers n, k, s (1 ≤ k ≤ n ≤ 150, 1 ≤ s ≤ 109) — the number of soldiers in the line, the size of the top-secret troop to be formed and the maximum possible number of swap operations of the consecutive pair of soldiers, respectively.

The second line of the input contains n integer qi (1 ≤ qi ≤ 1 000 000) — the values of loquacity of soldiers in order they follow in line from left to right.

## Output Format
Print a single integer — the minimum possible total loquacity of the top-secret troop.

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

## Note
In the first sample Colonel has to swap second and third soldiers, he doesn't really need the remaining swap. The resulting soldiers order is: (2, 1, 4). Minimum possible summary loquacity of the secret troop is 3. In the second sample Colonel will perform swaps in the following order:

1. (10, 1, 6 — 2, 5)
2. (10, 1, 2, 6 — 5)

The resulting soldiers order is (10, 1, 2, 5, 6).

Minimum possible summary loquacity is equal to 18.

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
Today is birthday of a Little Dasha — she is now 8 years old! On this occasion, each of her n friends and relatives gave her a ribbon with a greeting written on it, and, as it turned out, all the greetings are different. Dasha gathered all the ribbons and decided to throw away some of them in order to make the remaining set stylish. The birthday girl considers a set of ribbons stylish if no greeting written on some ribbon is a substring of another greeting written on some other ribbon. Let us recall that the substring of the string s is a continuous segment of s.

Help Dasha to keep as many ribbons as possible, so that she could brag about them to all of her friends. Dasha cannot rotate or flip ribbons, that is, each greeting can be read in a single way given in the input.

## Input Format
The first line of the input contains integer n (1 ≤ n ≤ 750) — the number of Dasha's relatives and friends.

Each of the next n lines contains exactly one greeting. Each greeting consists of characters 'a' and 'b' only.

The total length of all greetings won't exceed 10 000 000 characters.

## Output Format
In the first line print the maximum size of the stylish set. In the second line print the numbers of ribbons involved in it, assuming that they are numbered from 1 to n in the order they appear in the input. If there are several stylish sets of the maximum size, print any of them.

## Examples
```input
5
abab
aba
aabab
ababb
bab
```
```output
2
2 5
```

## Note
In the sample, the answer that keeps ribbons 3 and 4 is also considered correct.

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
Pasha has recently bought a new phone jPager and started adding his friends' phone numbers there. Each phone number consists of exactly n digits.

Also Pasha has a number k and two sequences of length n / k (n is divisible by k) a1, a2, ..., an / k and b1, b2, ..., bn / k. Let's split the phone number into blocks of length k. The first block will be formed by digits from the phone number that are on positions 1, 2,..., k, the second block will be formed by digits from the phone number that are on positions k + 1, k + 2, ..., 2·k and so on. Pasha considers a phone number good, if the i-th block doesn't start from the digit bi and is divisible by ai if represented as an integer.

To represent the block of length k as an integer, let's write it out as a sequence c1, c2,...,ck. Then the integer is calculated as the result of the expression c1·10k - 1 + c2·10k - 2 + ... + ck.

Pasha asks you to calculate the number of good phone numbers of length n, for the given k, ai and bi. As this number can be too big, print it modulo 109 + 7.

## Input Format
The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ min(n, 9)) — the length of all phone numbers and the length of each block, respectively. It is guaranteed that n is divisible by k.

The second line of the input contains n / k space-separated positive integers — sequence a1, a2, ..., an / k (1 ≤ ai < 10k).

The third line of the input contains n / k space-separated positive integers — sequence b1, b2, ..., bn / k (0 ≤ bi ≤ 9).

## Output Format
Print a single integer — the number of good phone numbers of length n modulo 109 + 7.

## Examples
```input
6 2
38 56 49
7 3 4
```
```output
8
```
-----
```input
8 2
1 22 3 44
5 4 3 2
```
```output
32400
```

## Note
In the first test sample good phone numbers are: 000000, 000098, 005600, 005698, 380000, 380098, 385600, 385698.

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
Saitama accidentally destroyed a hotel again. To repay the hotel company, Genos has volunteered to operate an elevator in one of its other hotels. The elevator is special — it starts on the top floor, can only move down, and has infinite capacity. Floors are numbered from 0 to s and elevator initially starts on floor s at time 0.

The elevator takes exactly 1 second to move down exactly 1 floor and negligible time to pick up passengers. Genos is given a list detailing when and on which floor passengers arrive. Please determine how long in seconds it will take Genos to bring all passengers to floor 0.

## Input Format
The first line of input contains two integers n and s (1 ≤ n ≤ 100, 1 ≤ s ≤ 1000) — the number of passengers and the number of the top floor respectively.

The next n lines each contain two space-separated integers fi and ti (1 ≤ fi ≤ s, 1 ≤ ti ≤ 1000) — the floor and the time of arrival in seconds for the passenger number i.

## Output Format
Print a single integer — the minimum amount of time in seconds needed to bring all the passengers to floor 0.

## Examples
```input
3 7
2 1
3 8
5 2
```
```output
11
```
-----
```input
5 10
2 77
3 33
8 21
9 12
10 64
```
```output
79
```

## Note
In the first sample, it takes at least 11 seconds to bring all passengers to floor 0. Here is how this could be done:

1. Move to floor 5: takes 2 seconds.

2. Pick up passenger 3.

3. Move to floor 3: takes 2 seconds.

4. Wait for passenger 2 to arrive: takes 4 seconds.

5. Pick up passenger 2.

6. Go to floor 2: takes 1 second.

7. Pick up passenger 1.

8. Go to floor 0: takes 2 seconds.

This gives a total of 2 + 2 + 4 + 1 + 2 = 11 seconds.

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
Pasha has a wooden stick of some positive integer length n. He wants to perform exactly three cuts to get four parts of the stick. Each part must have some positive integer length and the sum of these lengths will obviously be n.

Pasha likes rectangles but hates squares, so he wonders, how many ways are there to split a stick into four parts so that it's possible to form a rectangle using these parts, but is impossible to form a square.

Your task is to help Pasha and count the number of such ways. Two ways to cut the stick are considered distinct if there exists some integer x, such that the number of parts of length x in the first way differ from the number of parts of length x in the second way.

## Input Format
The first line of the input contains a positive integer n (1 ≤ n ≤ 2·109) — the length of Pasha's stick.

## Output Format
The output should contain a single integer — the number of ways to split Pasha's stick into four parts of positive integer length so that it's possible to make a rectangle by connecting the ends of these parts, but is impossible to form a square.

## Examples
```input
6
```
```output
1
```
-----
```input
20
```
```output
4
```

## Note
There is only one way to divide the stick in the first sample {1, 1, 2, 2}.

Four ways to divide the stick in the second sample are {1, 1, 9, 9}, {2, 2, 8, 8}, {3, 3, 7, 7} and {4, 4, 6, 6}. Note that {5, 5, 5, 5} doesn't work.

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
Vika has n jars with paints of distinct colors. All the jars are numbered from 1 to n and the i-th jar contains ai liters of paint of color i.

Vika also has an infinitely long rectangular piece of paper of width 1, consisting of squares of size 1 × 1. Squares are numbered 1, 2, 3 and so on. Vika decided that she will start painting squares one by one from left to right, starting from the square number 1 and some arbitrary color. If the square was painted in color x, then the next square will be painted in color x + 1. In case of x = n, next square is painted in color 1. If there is no more paint of the color Vika wants to use now, then she stops.

Square is always painted in only one color, and it takes exactly 1 liter of paint. Your task is to calculate the maximum number of squares that might be painted, if Vika chooses right color to paint the first square.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of jars with colors Vika has.

The second line of the input contains a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is equal to the number of liters of paint in the i-th jar, i.e. the number of liters of color i that Vika has.

## Output Format
The only line of the output should contain a single integer — the maximum number of squares that Vika can paint if she follows the rules described above.

## Examples
```input
5
2 4 2 3 3
```
```output
12
```
-----
```input
3
5 5 5
```
```output
15
```
-----
```input
6
10 10 10 1 10 10
```
```output
11
```

## Note
In the first sample the best strategy is to start painting using color 4. Then the squares will be painted in the following colors (from left to right): 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.

In the second sample Vika can start to paint using any color.

In the third sample Vika should start painting using color number 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 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
Statistics claims that students sleep no more than three hours a day. But even in the world of their dreams, while they are snoring peacefully, the sense of impending doom is still upon them.

A poor student is dreaming that he is sitting the mathematical analysis exam. And he is examined by the most formidable professor of all times, a three times Soviet Union Hero, a Noble Prize laureate in student expulsion, venerable Petr Palych.

The poor student couldn't answer a single question. Thus, instead of a large spacious office he is going to apply for a job to thorium mines. But wait a minute! Petr Palych decided to give the student the last chance! Yes, that is possible only in dreams.

So the professor began: "Once a Venusian girl and a Marsian boy met on the Earth and decided to take a walk holding hands. But the problem is the girl has al fingers on her left hand and ar fingers on the right one. The boy correspondingly has bl and br fingers. They can only feel comfortable when holding hands, when no pair of the girl's fingers will touch each other. That is, they are comfortable when between any two girl's fingers there is a boy's finger. And in addition, no three fingers of the boy should touch each other. Determine if they can hold hands so that the both were comfortable."

The boy any the girl don't care who goes to the left and who goes to the right. The difference is only that if the boy goes to the left of the girl, he will take her left hand with his right one, and if he goes to the right of the girl, then it is vice versa.

## Input Format
The first line contains two positive integers not exceeding 100. They are the number of fingers on the Venusian girl's left and right hand correspondingly. The second line contains two integers not exceeding 100. They are the number of fingers on the Marsian boy's left and right hands correspondingly.

## Output Format
Print YES or NO, that is, the answer to Petr Palych's question.

## Examples
```input
5 1
10 5
```
```output
YES
```
-----
```input
4 5
3 3
```
```output
YES
```
-----
```input
1 2
11 6
```
```output
NO
```

## Note
The boy and the girl don't really care who goes to the left.

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
Today, Wet Shark is given n integers. Using any of these integers no more than once, Wet Shark wants to get maximum possible even (divisible by 2) sum. Please, calculate this value for Wet Shark.

Note, that if Wet Shark uses no integers from the n integers, the sum is an even integer 0.

## Input Format
The first line of the input contains one integer, n (1 ≤ n ≤ 100 000). The next line contains n space separated integers given to Wet Shark. Each of these integers is in range from 1 to 109, inclusive.

## Output Format
Print the maximum possible even sum that can be obtained if we use some of the given integers.

## Examples
```input
3
1 2 3
```
```output
6
```
-----
```input
5
999999999 999999999 999999999 999999999 999999999
```
```output
3999999996
```

## Note
In the first sample, we can simply take all three integers for a total sum of 6.

In the second sample Wet Shark should take any four out of five integers 999 999 999.

Now solve the problem and return the code.