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
Merge sort is a well-known sorting algorithm. The main function that sorts the elements of array a with indices from [l, r) can be implemented as follows:

1. If the segment [l, r) is already sorted in non-descending order (that is, for any i such that l ≤ i < r - 1 a[i] ≤ a[i + 1]), then end the function call;
2. Let $$mid = \left\lfloor \frac{l+r}{2} \right\rfloor$$;
3. Call mergesort(a, l, mid);
4. Call mergesort(a, mid, r);
5. Merge segments [l, mid) and [mid, r), making the segment [l, r) sorted in non-descending order. The merge algorithm doesn't call any other functions.

The array in this problem is 0-indexed, so to sort the whole array, you need to call mergesort(a, 0, n).

The number of calls of function mergesort is very important, so Ivan has decided to calculate it while sorting the array. For example, if a = {1, 2, 3, 4}, then there will be 1 call of mergesort — mergesort(0, 4), which will check that the array is sorted and then end. If a = {2, 1, 3}, then the number of calls is 3: first of all, you call mergesort(0, 3), which then sets mid = 1 and calls mergesort(0, 1) and mergesort(1, 3), which do not perform any recursive calls because segments (0, 1) and (1, 3) are sorted.

Ivan has implemented the program that counts the number of mergesort calls, but now he needs to test it. To do this, he needs to find an array a such that a is a permutation of size n (that is, the number of elements in a is n, and every integer number from [1, n] can be found in this array), and the number of mergesort calls when sorting the array is exactly k.

Help Ivan to find an array he wants!

## Input Format
The first line contains two numbers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 200000) — the size of a desired permutation and the number of mergesort calls required to sort it.

## Output Format
If a permutation of size n such that there will be exactly k calls of mergesort while sorting it doesn't exist, output  - 1. Otherwise output n integer numbers a[0], a[1], ..., a[n - 1] — the elements of a permutation that would meet the required conditions. If there are multiple answers, print any of them.

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

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
Alexey recently held a programming contest for students from Berland. n students participated in a contest, i-th of them solved ai problems. Now he wants to award some contestants. Alexey can award the students with diplomas of three different degrees. Each student either will receive one diploma of some degree, or won't receive any diplomas at all. Let cntx be the number of students that are awarded with diplomas of degree x (1 ≤ x ≤ 3). The following conditions must hold:

- For each x (1 ≤ x ≤ 3) cntx > 0;
- For any two degrees x and y cntx ≤ 2·cnty.

Of course, there are a lot of ways to distribute the diplomas. Let bi be the degree of diploma i-th student will receive (or  - 1 if i-th student won't receive any diplomas). Also for any x such that 1 ≤ x ≤ 3 let cx be the maximum number of problems solved by a student that receives a diploma of degree x, and dx be the minimum number of problems solved by a student that receives a diploma of degree x. Alexey wants to distribute the diplomas in such a way that:

1. If student i solved more problems than student j, then he has to be awarded not worse than student j (it's impossible that student j receives a diploma and i doesn't receive any, and also it's impossible that both of them receive a diploma, but bj < bi);
2. d1 - c2 is maximum possible;
3. Among all ways that maximize the previous expression, d2 - c3 is maximum possible;
4. Among all ways that correspond to the two previous conditions, d3 - c - 1 is maximum possible, where c - 1 is the maximum number of problems solved by a student that doesn't receive any diploma (or 0 if each student is awarded with some diploma).

Help Alexey to find a way to award the contestants!

## Input Format
The first line contains one integer number n (3 ≤ n ≤ 3000).

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 5000).

## Output Format
Output n numbers. i-th number must be equal to the degree of diploma i-th contestant will receive (or  - 1 if he doesn't receive any diploma).

If there are multiple optimal solutions, print any of them. It is guaranteed that the answer always exists.

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

# Problem
You are given a string s consisting of n lowercase Latin letters. Some indices in this string are marked as forbidden.

You want to find a string a such that the value of |a|·f(a) is maximum possible, where f(a) is the number of occurences of a in s such that these occurences end in non-forbidden indices. So, for example, if s is aaaa, a is aa and index 3 is forbidden, then f(a) = 2 because there are three occurences of a in s (starting in indices 1, 2 and 3), but one of them (starting in index 2) ends in a forbidden index.

Calculate the maximum possible value of |a|·f(a) you can get.

## Input Format
The first line contains an integer number n (1 ≤ n ≤ 200000) — the length of s.

The second line contains a string s, consisting of n lowercase Latin letters.

The third line contains a string t, consisting of n characters 0 and 1. If i-th character in t is 1, then i is a forbidden index (otherwise i is not forbidden).

## Output Format
Print the maximum possible value of |a|·f(a).

## Examples
```input
5
ababa
00100
```
```output
5
```
-----
```input
5
ababa
00000
```
```output
6
```
-----
```input
5
ababa
11111
```
```output
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
Vasya studies music.

He has learned lots of interesting stuff. For example, he knows that there are 12 notes: C, C#, D, D#, E, F, F#, G, G#, A, B, H. He also knows that the notes are repeated cyclically: after H goes C again, and before C stands H. We will consider the C note in the row's beginning and the C note after the H similar and we will identify them with each other. The distance between the notes along the musical scale is measured in tones: between two consecutive notes there's exactly one semitone, that is, 0.5 tone. The distance is taken from the lowest tone to the uppest one, that is, the distance between C and E is 4 semitones and between E and C is 8 semitones

Vasya also knows what a chord is. A chord is an unordered set of no less than three notes. However, for now Vasya only works with triads, that is with the chords that consist of exactly three notes. He can already distinguish between two types of triads — major and minor.

Let's define a major triad. Let the triad consist of notes X, Y and Z. If we can order the notes so as the distance along the musical scale between X and Y equals 4 semitones and the distance between Y and Z is 3 semitones, then the triad is major. The distance between X and Z, accordingly, equals 7 semitones.

A minor triad is different in that the distance between X and Y should be 3 semitones and between Y and Z — 4 semitones.

For example, the triad "C E G" is major: between C and E are 4 semitones, and between E and G are 3 semitones. And the triplet "C# B F" is minor, because if we order the notes as "B C# F", than between B and C# will be 3 semitones, and between C# and F — 4 semitones.

Help Vasya classify the triad the teacher has given to him.

## Input Format
The only line contains 3 space-separated notes in the above-given notation.

## Output Format
Print "major" if the chord is major, "minor" if it is minor, and "strange" if the teacher gave Vasya some weird chord which is neither major nor minor. Vasya promises you that the answer will always be unambiguous. That is, there are no chords that are both major and minor simultaneously.

## Examples
```input
C E G
```
```output
major
```
-----
```input
C# B F
```
```output
minor
```
-----
```input
A B H
```
```output
strange
```

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
Vasya learns to type. He has an unusual keyboard at his disposal: it is rectangular and it has n rows of keys containing m keys in each row. Besides, the keys are of two types. Some of the keys have lowercase Latin letters on them and some of the keys work like the "Shift" key on standard keyboards, that is, they make lowercase letters uppercase.

Vasya can press one or two keys with one hand. However, he can only press two keys if the Euclidean distance between the centers of the keys does not exceed x. The keys are considered as squares with a side equal to 1. There are no empty spaces between neighbouring keys.

Vasya is a very lazy boy, that's why he tries to type with one hand as he eats chips with his other one. However, it is possible that some symbol can't be typed with one hand only, because the distance between it and the closest "Shift" key is strictly larger than x. In this case he will have to use his other hand. Having typed the symbol, Vasya returns other hand back to the chips.

You are given Vasya's keyboard and the text. Count the minimum number of times Vasya will have to use the other hand.

## Input Format
The first line contains three integers n, m, x (1 ≤ n, m ≤ 30, 1 ≤ x ≤ 50).

Next n lines contain descriptions of all the keyboard keys. Each line contains the descriptions of exactly m keys, without spaces. The letter keys are marked with the corresponding lowercase letters. The "Shift" keys are marked with the "S" symbol.

Then follow the length of the text q (1 ≤ q ≤ 5·105). The last line contains the text T, which consists of q symbols, which are uppercase and lowercase Latin letters.

## Output Format
If Vasya can type the text, then print the minimum number of times he will have to use his other hand. Otherwise, print "-1" (without the quotes).

## Examples
```input
2 2 1
ab
cd
1
A
```
```output
-1
```
-----
```input
2 2 1
ab
cd
1
e
```
```output
-1
```
-----
```input
2 2 1
ab
cS
5
abcBA
```
```output
1
```
-----
```input
3 9 4
qwertyuio
asdfghjkl
SzxcvbnmS
35
TheQuIcKbRoWnFOXjummsovertHeLazYDOG
```
```output
2
```

## Note
In the first sample the symbol "A" is impossible to print as there's no "Shift" key on the keyboard.

In the second sample the symbol "e" is impossible to print as there's no such key on the keyboard.

In the fourth sample the symbols "T", "G" are impossible to print with one hand. The other letters that are on the keyboard can be printed. Those symbols come up in the text twice, thus, the answer is 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: 2.5 seconds
Memory limit: 256.0 MB

# Problem
Lakhesh loves to make movies, so Nephren helps her run a cinema. We may call it No. 68 Cinema.

However, one day, the No. 68 Cinema runs out of changes (they don't have 50-yuan notes currently), but Nephren still wants to start their business. (Assume that yuan is a kind of currency in Regulu Ere.)

There are three types of customers: some of them bring exactly a 50-yuan note; some of them bring a 100-yuan note and Nephren needs to give a 50-yuan note back to him/her; some of them bring VIP cards so that they don't need to pay for the ticket.

Now n customers are waiting outside in queue. Nephren wants to know how many possible queues are there that they are able to run smoothly (i.e. every customer can receive his/her change), and that the number of 50-yuan notes they have after selling tickets to all these customers is between l and r, inclusive. Two queues are considered different if there exists a customer whose type is different in two queues. As the number can be large, please output the answer modulo p.

## Input Format
One line containing four integers n (1 ≤ n ≤ 105), p (1 ≤ p ≤ 2·109), l and r (0 ≤ l ≤ r ≤ n).

## Output Format
One line indicating the answer modulo p.

## Examples
```input
4 97 2 3
```
```output
13
```
-----
```input
4 100 0 4
```
```output
35
```

## Note
We use A, B and C to indicate customers with 50-yuan notes, customers with 100-yuan notes and customers with VIP cards respectively.

For the first sample, the different possible queues that there are 2 50-yuan notes left are AAAB, AABA, ABAA, AACC, ACAC, ACCA, CAAC, CACA and CCAA, and the different possible queues that there are 3 50-yuan notes left are AAAC, AACA, ACAA and CAAA. So there are 13 different queues satisfying the first sample. Similarly, there are 35 different queues satisfying the second sample.

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 group of university students wants to get to the top of a mountain to have a picnic there. For that they decided to use a cableway.

A cableway is represented by some cablecars, hanged onto some cable stations by a cable. A cable is scrolled cyclically between the first and the last cable stations (the first of them is located at the bottom of the mountain and the last one is located at the top). As the cable moves, the cablecar attached to it move as well.

The number of cablecars is divisible by three and they are painted three colors: red, green and blue, in such manner that after each red cablecar goes a green one, after each green cablecar goes a blue one and after each blue cablecar goes a red one. Each cablecar can transport no more than two people, the cablecars arrive with the periodicity of one minute (i. e. every minute) and it takes exactly 30 minutes for a cablecar to get to the top.

All students are divided into three groups: r of them like to ascend only in the red cablecars, g of them prefer only the green ones and b of them prefer only the blue ones. A student never gets on a cablecar painted a color that he doesn't like,

The first cablecar to arrive (at the moment of time 0) is painted red. Determine the least time it will take all students to ascend to the mountain top.

## Input Format
The first line contains three integers r, g and b (0 ≤ r, g, b ≤ 100). It is guaranteed that r + g + b > 0, it means that the group consists of at least one student.

## Output Format
Print a single number — the minimal time the students need for the whole group to ascend to the top of the mountain.

## Examples
```input
1 3 2
```
```output
34
```
-----
```input
3 2 1
```
```output
33
```

## Note
Let's analyze the first sample.

At the moment of time 0 a red cablecar comes and one student from the r group get on it and ascends to the top at the moment of time 30.

At the moment of time 1 a green cablecar arrives and two students from the g group get on it; they get to the top at the moment of time 31.

At the moment of time 2 comes the blue cablecar and two students from the b group get on it. They ascend to the top at the moment of time 32.

At the moment of time 3 a red cablecar arrives but the only student who is left doesn't like red and the cablecar leaves empty.

At the moment of time 4 a green cablecar arrives and one student from the g group gets on it. He ascends to top at the moment of time 34.

Thus, all the students are on the top, overall the ascension took exactly 34 minutes.

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
Mishka has got n empty boxes. For every i (1 ≤ i ≤ n), i-th box is a cube with side length ai.

Mishka can put a box i into another box j if the following conditions are met:

- i-th box is not put into another box;
- j-th box doesn't contain any other boxes;
- box i is smaller than box j (ai < aj).

Mishka can put boxes into each other an arbitrary number of times. He wants to minimize the number of visible boxes. A box is called visible iff it is not put into some another box.

Help Mishka to determine the minimum possible number of visible boxes!

## Input Format
The first line contains one integer n (1 ≤ n ≤ 5000) — the number of boxes Mishka has got.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the side length of i-th box.

## Output Format
Print the minimum possible number of visible boxes.

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

## Note
In the first example it is possible to put box 1 into box 2, and 2 into 3.

In the second example Mishka can put box 2 into box 3, and box 4 into box 1.

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
Let's denote a function

$$d(x,y) = \begin{cases} y - x, & \text{if } |x-y| > 1 \\ 0, & \text{if } |x-y| \leq 1 \end{cases}$$

You are given an array a consisting of n integers. You have to calculate the sum of d(ai, aj) over all pairs (i, j) such that 1 ≤ i ≤ j ≤ n.

## Input Format
The first line contains one integer n (1 ≤ n ≤ 200000) — the number of elements in a.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — elements of the array.

## Output Format
Print one integer — the sum of d(ai, aj) over all pairs (i, j) such that 1 ≤ i ≤ j ≤ n.

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

## Note
In the first example:

1. d(a1, a2) = 0;
2. d(a1, a3) = 2;
3. d(a1, a4) = 0;
4. d(a1, a5) = 2;
5. d(a2, a3) = 0;
6. d(a2, a4) = 0;
7. d(a2, a5) = 0;
8. d(a3, a4) =  - 2;
9. d(a3, a5) = 0;
10. d(a4, a5) = 2.

Now solve the problem and return the code.