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
A teacher decides to give toffees to his students. He asks n students to stand in a queue. Since the teacher is very partial, he follows the following rule to distribute toffees.

He looks at the first two students and gives more toffees to the student having higher marks than the other one. If they have the same marks they get the same number of toffees. The same procedure is followed for each pair of adjacent students starting from the first one to the last one.

It is given that each student receives at least one toffee. You have to find the number of toffees given to each student by the teacher such that the total number of toffees is minimum.

## Input Format
The first line of input contains the number of students n (2 ≤ n ≤ 1000). The second line gives (n - 1) characters consisting of "L", "R" and "=". For each pair of adjacent students "L" means that the left student has higher marks, "R" means that the right student has higher marks and "=" means that both have equal marks.

## Output Format
Output consists of n integers separated by a space representing the number of toffees each student receives in the queue starting from the first one to the last one.

## Examples
```input
5
LRLR
```
```output
2 1 2 1 2
```
-----
```input
5
=RRR
```
```output
1 1 2 3 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let A = {a1, a2, ..., an} be any permutation of the first n natural numbers {1, 2, ..., n}. You are given a positive integer k and another sequence B = {b1, b2, ..., bn}, where bi is the number of elements aj in A to the left of the element at = i such that aj ≥ (i + k).

For example, if n = 5, a possible A is {5, 1, 4, 2, 3}. For k = 2, B is given by {1, 2, 1, 0, 0}. But if k = 3, then B = {1, 1, 0, 0, 0}.

For two sequences X = {x1, x2, ..., xn} and Y = {y1, y2, ..., yn}, let i-th elements be the first elements such that xi ≠ yi. If xi < yi, then X is lexicographically smaller than Y, while if xi > yi, then X is lexicographically greater than Y.

Given n, k and B, you need to determine the lexicographically smallest A.

## Input Format
The first line contains two space separated integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n). On the second line are n integers specifying the values of B = {b1, b2, ..., bn}.

## Output Format
Print on a single line n integers of A = {a1, a2, ..., an} such that A is lexicographically minimal. It is guaranteed that the solution exists.

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

# Problem
You are given a sequence of balls A by your teacher, each labeled with a lowercase Latin letter 'a'-'z'. You don't like the given sequence. You want to change it into a new sequence, B that suits you better. So, you allow yourself four operations:

- You can insert any ball with any label into the sequence at any position.
- You can delete (remove) any ball from any position.
- You can replace any ball with any other ball.
- You can exchange (swap) two adjacent balls.

Your teacher now places time constraints on each operation, meaning that an operation can only be performed in certain time. So, the first operation takes time ti, the second one takes td, the third one takes tr and the fourth one takes te. Also, it is given that 2·te ≥ ti + td.

Find the minimal time to convert the sequence A to the sequence B.

## Input Format
The first line contains four space-separated integers ti, td, tr, te (0 < ti, td, tr, te ≤ 100). The following two lines contain sequences A and B on separate lines. The length of each line is between 1 and 4000 characters inclusive.

## Output Format
Print a single integer representing minimum time to convert A into B.

## Examples
```input
1 1 1 1
youshouldnot
thoushaltnot
```
```output
5
```
-----
```input
2 4 10 3
ab
ba
```
```output
3
```
-----
```input
1 10 20 30
a
za
```
```output
1
```

## Note
In the second sample, you could delete the ball labeled 'a' from the first position and then insert another 'a' at the new second position with total time 6. However exchanging the balls give total time 3.

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

# Problem
Professor Phunsuk Wangdu has performed some experiments on rays. The setup for n rays is as follows.

There is a rectangular box having exactly n holes on the opposite faces. All rays enter from the holes of the first side and exit from the holes of the other side of the box. Exactly one ray can enter or exit from each hole. The holes are in a straight line.

Professor Wangdu is showing his experiment to his students. He shows that there are cases, when all the rays are intersected by every other ray. A curious student asked the professor: "Sir, there are some groups of rays such that all rays in that group intersect every other ray in that group. Can we determine the number of rays in the largest of such groups?".

Professor Wangdu now is in trouble and knowing your intellect he asks you to help him.

## Input Format
The first line contains n (1 ≤ n ≤ 106), the number of rays. The second line contains n distinct integers. The i-th integer xi (1 ≤ xi ≤ n) shows that the xi-th ray enters from the i-th hole. Similarly, third line contains n distinct integers. The i-th integer yi (1 ≤ yi ≤ n) shows that the yi-th ray exits from the i-th hole. All rays are numbered from 1 to n.

## Output Format
Output contains the only integer which is the number of rays in the largest group of rays all of which intersect each other.

## Examples
```input
5
1 4 5 2 3
3 4 2 1 5
```
```output
3
```
-----
```input
3
3 1 2
2 3 1
```
```output
2
```

## Note
For the first test case, the figure is shown above. The output of the first test case is 3, since the rays number 1, 4 and 3 are the ones which are intersected by each other one i.e. 1 is intersected by 4 and 3, 3 is intersected by 4 and 1, and 4 is intersected by 1 and 3. Hence every ray in this group is intersected by each other one. There does not exist any group containing more than 3 rays satisfying the above-mentioned constraint.

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
Every year, hundreds of people come to summer camps, they learn new algorithms and solve hard problems.

This is your first year at summer camp, and you are asked to solve the following problem. All integers starting with 1 are written in one line. The prefix of these line is "123456789101112131415...". Your task is to print the n-th digit of this string (digits are numbered starting with 1.

## Input Format
The only line of the input contains a single integer n (1 ≤ n ≤ 1000) — the position of the digit you need to print.

## Output Format
Print the n-th digit of the line.

## Examples
```input
3
```
```output
3
```
-----
```input
11
```
```output
0
```

## Note
In the first sample the digit at position 3 is '3', as both integers 1 and 2 consist on one digit.

In the second sample, the digit at position 11 is '0', it belongs to the integer 10.

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 wise man told Kerem "Different is good" once, so Kerem wants all things in his life to be different.

Kerem recently got a string s consisting of lowercase English letters. Since Kerem likes it when things are different, he wants all substrings of his string s to be distinct. Substring is a string formed by some number of consecutive characters of the string. For example, string "aba" has substrings "" (empty substring), "a", "b", "a", "ab", "ba", "aba".

If string s has at least two equal substrings then Kerem will change characters at some positions to some other lowercase English letters. Changing characters is a very tiring job, so Kerem want to perform as few changes as possible.

Your task is to find the minimum number of changes needed to make all the substrings of the given string distinct, or determine that it is impossible.

## Input Format
The first line of the input contains an integer n (1 ≤ n ≤ 100 000) — the length of the string s.

The second line contains the string s of length n consisting of only lowercase English letters.

## Output Format
If it's impossible to change the string s such that all its substring are distinct print -1. Otherwise print the minimum required number of changes.

## Examples
```input
2
aa
```
```output
1
```
-----
```input
4
koko
```
```output
2
```
-----
```input
5
murat
```
```output
0
```

## Note
In the first sample one of the possible solutions is to change the first character to 'b'.

In the second sample, one may change the first character to 'a' and second character to 'b', so the string becomes "abko".

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
Vanya smashes potato in a vertical food processor. At each moment of time the height of the potato in the processor doesn't exceed h and the processor smashes k centimeters of potato each second. If there are less than k centimeters remaining, than during this second processor smashes all the remaining potato.

Vanya has n pieces of potato, the height of the i-th piece is equal to ai. He puts them in the food processor one by one starting from the piece number 1 and finishing with piece number n. Formally, each second the following happens:

1. If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece.
2. Processor smashes k centimeters of potato (or just everything that is inside).

Provided the information about the parameter of the food processor and the size of each potato in a row, compute how long will it take for all the potato to become smashed.

## Input Format
The first line of the input contains integers n, h and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 109) — the number of pieces of potato, the height of the food processor and the amount of potato being smashed each second, respectively.

The second line contains n integers ai (1 ≤ ai ≤ h) — the heights of the pieces.

## Output Format
Print a single integer — the number of seconds required to smash all the potatoes following the process described in the problem statement.

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

## Note
Consider the first sample.

1. First Vanya puts the piece of potato of height 5 into processor. At the end of the second there is only amount of height 2 remaining inside.
2. Now Vanya puts the piece of potato of height 4. At the end of the second there is amount of height 3 remaining.
3. Vanya puts the piece of height 3 inside and again there are only 3 centimeters remaining at the end of this second.
4. Vanya finally puts the pieces of height 2 and 1 inside. At the end of the second the height of potato in the processor is equal to 3.
5. During this second processor finally smashes all the remaining potato and the process finishes.

In the second sample, Vanya puts the piece of height 5 inside and waits for 2 seconds while it is completely smashed. Then he repeats the same process for 4 other pieces. The total time is equal to 2·5 = 10 seconds.

In the third sample, Vanya simply puts all the potato inside the processor and waits 2 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
While walking down the street Vanya saw a label "Hide&Seek". Because he is a programmer, he used & as a bitwise AND for these two words represented as a integers in base 64 and got new word. Now Vanya thinks of some string s and wants to know the number of pairs of words of length |s| (length of s), such that their bitwise AND is equal to s. As this number can be large, output it modulo 109 + 7.

To represent the string as a number in numeral system with base 64 Vanya uses the following rules:

- digits from '0' to '9' correspond to integers from 0 to 9;
- letters from 'A' to 'Z' correspond to integers from 10 to 35;
- letters from 'a' to 'z' correspond to integers from 36 to 61;
- letter '-' correspond to integer 62;
- letter '_' correspond to integer 63.

## Input Format
The only line of the input contains a single word s (1 ≤ |s| ≤ 100 000), consisting of digits, lowercase and uppercase English letters, characters '-' and '_'.

## Output Format
Print a single integer — the number of possible pairs of words, such that their bitwise AND is equal to string s modulo 109 + 7.

## Examples
```input
z
```
```output
3
```
-----
```input
V_V
```
```output
9
```
-----
```input
Codeforces
```
```output
130653412
```

## Note
For a detailed definition of bitwise AND we recommend to take a look in the corresponding article in Wikipedia.

In the first sample, there are 3 possible solutions:

1. z&_ = 61&63 = 61 = z
2. _&z = 63&61 = 61 = z
3. z&z = 61&61 = 61 = z

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
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 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
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 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
On the coordinate plane there is a square with sides parallel to the coordinate axes. The length of the square side is equal to a. The lower left corner of the square coincides with the point (0, 0) (the point of the origin). The upper right corner of the square has positive coordinates.

You are given a point with coordinates (x, y). Your task is to determine whether this point is located strictly inside the square, on its side, or strictly outside the square.

## Input Format
The first line contains three integers a, x and y (1 ≤ a ≤ 1000,  - 1000 ≤ x, y ≤ 1000) — the length of the square side and the coordinates of the point which should be checked.

## Output Format
Print one integer:

- 0, if the point is located strictly inside the square;
- 1, if the point is located on the side of the square;
- 2, if the point is located strictly outside the square.

## Examples
```input
2 1 1
```
```output
0
```
-----
```input
4 4 4
```
```output
1
```
-----
```input
10 5 -4
```
```output
2
```

Now solve the problem and return the code.