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
Berlanders like to eat cones after a hard day. Misha Square and Sasha Circle are local authorities of Berland. Each of them controls its points of cone trade. Misha has n points, Sasha — m. Since their subordinates constantly had conflicts with each other, they decided to build a fence in the form of a circle, so that the points of trade of one businessman are strictly inside a circle, and points of the other one are strictly outside. It doesn't matter which of the two gentlemen will have his trade points inside the circle.

Determine whether they can build a fence or not.

## Input Format
The first line contains two integers n and m (1 ≤ n, m ≤ 10000), numbers of Misha's and Sasha's trade points respectively.

The next n lines contains pairs of space-separated integers Mx, My ( - 104 ≤ Mx, My ≤ 104), coordinates of Misha's trade points.

The next m lines contains pairs of space-separated integers Sx, Sy ( - 104 ≤ Sx, Sy ≤ 104), coordinates of Sasha's trade points.

It is guaranteed that all n + m points are distinct.

## Output Format
The only output line should contain either word "YES" without quotes in case it is possible to build a such fence or word "NO" in the other case.

## Examples
```input
2 2
-1 0
1 0
0 -1
0 1
```
```output
NO
```
-----
```input
4 4
1 0
0 1
-1 0
0 -1
1 1
-1 1
-1 -1
1 -1
```
```output
YES
```

## Note
In the first sample there is no possibility to separate points, because any circle that contains both points ( - 1, 0), (1, 0) also contains at least one point from the set (0,  - 1), (0, 1), and vice-versa: any circle that contains both points (0,  - 1), (0, 1) also contains at least one point from the set ( - 1, 0), (1, 0)

In the second sample one of the possible solution is shown below. Misha's points are marked with red colour and Sasha's are marked with blue.

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
Do you like summer? Residents of Berland do. They especially love eating ice cream in the hot summer. So this summer day a large queue of n Berland residents lined up in front of the ice cream stall. We know that each of them has a certain amount of berland dollars with them. The residents of Berland are nice people, so each person agrees to swap places with the person right behind him for just 1 dollar. More formally, if person a stands just behind person b, then person a can pay person b 1 dollar, then a and b get swapped. Of course, if person a has zero dollars, he can not swap places with person b.

Residents of Berland are strange people. In particular, they get upset when there is someone with a strictly smaller sum of money in the line in front of them.

Can you help the residents of Berland form such order in the line so that they were all happy? A happy resident is the one who stands first in the line or the one in front of who another resident stands with not less number of dollars. Note that the people of Berland are people of honor and they agree to swap places only in the manner described above.

## Input Format
The first line contains integer n (1 ≤ n ≤ 200 000) — the number of residents who stand in the line.

The second line contains n space-separated integers ai (0 ≤ ai ≤ 109), where ai is the number of Berland dollars of a man standing on the i-th position in the line. The positions are numbered starting from the end of the line.

## Output Format
If it is impossible to make all the residents happy, print ":(" without the quotes. Otherwise, print in the single line n space-separated integers, the i-th of them must be equal to the number of money of the person on position i in the new line. If there are multiple answers, print any of them.

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

## Note
In the first sample two residents should swap places, after that the first resident has 10 dollars and he is at the head of the line and the second resident will have 9 coins and he will be at the end of the line.

In the second sample it is impossible to achieve the desired result.

In the third sample the first person can swap with the second one, then they will have the following numbers of dollars: 4 11 3, then the second person (in the new line) swaps with the third one, and the resulting numbers of dollars will equal to: 4 4 10. In this line everybody will be happy.

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
The determinant of a matrix 2 × 2 is defined as follows:

$$\operatorname*{det}\left(\begin{array}{cc}
a & b \\
c & d
\end{array}\right) = ad - bc$$

A matrix is called degenerate if its determinant is equal to zero.

The norm ||A|| of a matrix A is defined as a maximum of absolute values of its elements.

You are given a matrix $${\boldsymbol{A}}={\begin{pmatrix}a&b\\c&d\end{pmatrix}}$$. Consider any degenerate matrix B such that norm ||A - B|| is minimum possible. Determine ||A - B||.

## Input Format
The first line contains two integers a and b (|a|, |b| ≤ 109), the elements of the first row of matrix A.

The second line contains two integers c and d (|c|, |d| ≤ 109) the elements of the second row of matrix A.

## Output Format
Output a single real number, the minimum possible value of ||A - B||. Your answer is considered to be correct if its absolute or relative error does not exceed 10 - 9.

## Examples
```input
1 2
3 4
```
```output
0.2000000000
```
-----
```input
1 0
0 1
```
```output
0.5000000000
```

## Note
In the first sample matrix B is $${ \left( \begin{array} { l l } { 1. 2 } & { 1. 8 } \\ { 2. 8 } & { 4. 2 } \end{array} \right) }$$

In the second sample matrix B is $${ \left( \begin{array} { l l } { 0. 5 } & { 0. 5 } \\ { 0. 5 } & { 0. 5 } \end{array} \right) }$$

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
Professor GukiZ likes programming contests. He especially likes to rate his students on the contests he prepares. Now, he has decided to prepare a new contest.

In total, n students will attend, and before the start, every one of them has some positive integer rating. Students are indexed from 1 to n. Let's denote the rating of i-th student as ai. After the contest ends, every student will end up with some positive integer position. GukiZ expects that his students will take places according to their ratings.

He thinks that each student will take place equal to $$1 + (\text{number of students with strictly higher rating than his or her})$$. In particular, if student A has rating strictly lower then student B, A will get the strictly better position than B, and if two students have equal ratings, they will share the same position.

GukiZ would like you to reconstruct the results by following his expectations. Help him and determine the position after the end of the contest for each of his students if everything goes as expected.

## Input Format
The first line contains integer n (1 ≤ n ≤ 2000), number of GukiZ's students.

The second line contains n numbers a1, a2, ... an (1 ≤ ai ≤ 2000) where ai is the rating of i-th student (1 ≤ i ≤ n).

## Output Format
In a single line, print the position after the end of the contest for each of n students in the same order as they appear in the input.

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

## Note
In the first sample, students 2 and 3 are positioned first (there is no other student with higher rating), and student 1 is positioned third since there are two students with higher rating.

In the second sample, first student is the only one on the contest.

In the third sample, students 2 and 5 share the first position with highest rating, student 4 is next with third position, and students 1 and 3 are the last sharing fourth position.

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
Professor GukiZ is concerned about making his way to school, because massive piles of boxes are blocking his way.

In total there are n piles of boxes, arranged in a line, from left to right, i-th pile (1 ≤ i ≤ n) containing ai boxes. Luckily, m students are willing to help GukiZ by removing all the boxes from his way. Students are working simultaneously. At time 0, all students are located left of the first pile. It takes one second for every student to move from this position to the first pile, and after that, every student must start performing sequence of two possible operations, each taking one second to complete. Possible operations are:

1. If i ≠ n, move from pile i to pile i + 1;
2. If pile located at the position of student is not empty, remove one box from it.

GukiZ's students aren't smart at all, so they need you to tell them how to remove boxes before professor comes (he is very impatient man, and doesn't want to wait). They ask you to calculate minumum time t in seconds for which they can remove all the boxes from GukiZ's way. Note that students can be positioned in any manner after t seconds, but all the boxes must be removed.

## Input Format
The first line contains two integers n and m (1 ≤ n, m ≤ 105), the number of piles of boxes and the number of GukiZ's students.

The second line contains n integers a1, a2, ... an (0 ≤ ai ≤ 109) where ai represents the number of boxes on i-th pile. It's guaranteed that at least one pile of is non-empty.

## Output Format
In a single line, print one number, minimum time needed to remove all the boxes in seconds.

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

## Note
First sample: Student will first move to the first pile (1 second), then remove box from first pile (1 second), then move to the second pile (1 second) and finally remove the box from second pile (1 second).

Second sample: One of optimal solutions is to send one student to remove a box from the first pile and a box from the third pile, and send another student to remove a box from the third pile. Overall, 5 seconds.

Third sample: With a lot of available students, send three of them to remove boxes from the first pile, four of them to remove boxes from the second pile, five of them to remove boxes from the third pile, and four of them to remove boxes from the fourth pile. Process will be over in 5 seconds, when removing the boxes from the last pile is finished.

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
We all know that GukiZ often plays with arrays.

Now he is thinking about this problem: how many arrays a, of length n, with non-negative elements strictly less then 2l meet the following condition: $$(a_{1}\ \mathrm{and}\ a_{2})\ \mathrm{or}\ (a_{2}\ \mathrm{and}\ a_{3})\ \mathrm{or}\ldots\ \mathrm{or}\ (a_{n-1}\ \mathrm{and}\ a_{n})=k$$? Here operation $$\text{and}$$ means bitwise AND (in Pascal it is equivalent to and, in C/C++/Java/Python it is equivalent to &), operation $$\sigma_{1}^{2}$$ means bitwise OR (in Pascal it is equivalent to $$\sigma_{1}^{2}$$, in C/C++/Java/Python it is equivalent to |).

Because the answer can be quite large, calculate it modulo m. This time GukiZ hasn't come up with solution, and needs you to help him!

## Input Format
First and the only line of input contains four integers n, k, l, m (2 ≤ n ≤ 1018, 0 ≤ k ≤ 1018, 0 ≤ l ≤ 64, 1 ≤ m ≤ 109 + 7).

## Output Format
In the single line print the number of arrays satisfying the condition above modulo m.

## Examples
```input
2 1 2 10
```
```output
3
```
-----
```input
2 1 1 3
```
```output
1
```
-----
```input
3 3 2 10
```
```output
9
```

## Note
In the first sample, satisfying arrays are {1, 1}, {3, 1}, {1, 3}.

In the second sample, only satisfying array is {1, 1}.

In the third sample, satisfying arrays are {0, 3, 3}, {1, 3, 2}, {1, 3, 3}, {2, 3, 1}, {2, 3, 3}, {3, 3, 0}, {3, 3, 1}, {3, 3, 2}, {3, 3, 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: 10.0 seconds
Memory limit: 256.0 MB

# Problem
Professor GukiZ was playing with arrays again and accidentally discovered new function, which he called GukiZiana. For given array a, indexed with integers from 1 to n, and number y, GukiZiana(a, y) represents maximum value of j - i, such that aj = ai = y. If there is no y as an element in a, then GukiZiana(a, y) is equal to  - 1. GukiZ also prepared a problem for you. This time, you have two types of queries:

1. First type has form 1 l r x and asks you to increase values of all ai such that l ≤ i ≤ r by the non-negative integer x.
2. Second type has form 2 y and asks you to find value of GukiZiana(a, y).

For each query of type 2, print the answer and make GukiZ happy!

## Input Format
The first line contains two integers n, q (1 ≤ n ≤ 5 * 105, 1 ≤ q ≤ 5 * 104), size of array a, and the number of queries.

The second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 109), forming an array a.

Each of next q lines contain either four or two numbers, as described in statement:

If line starts with 1, then the query looks like 1 l r x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109), first type query.

If line starts with 2, then th query looks like 2 y (1 ≤ y ≤ 109), second type query.

## Output Format
For each query of type 2, print the value of GukiZiana(a, y), for y value for that query.

## Examples
```input
4 3
1 2 3 4
1 1 2 1
1 1 1 1
2 3
```
```output
2
```
-----
```input
2 3
1 2
1 2 2 1
2 3
2 4
```
```output
0
-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
A magic island Geraldion, where Gerald lives, has its own currency system. It uses banknotes of several values. But the problem is, the system is not perfect and sometimes it happens that Geraldionians cannot express a certain sum of money with any set of banknotes. Of course, they can use any number of banknotes of each value. Such sum is called unfortunate. Gerald wondered: what is the minimum unfortunate sum?

## Input Format
The first line contains number n (1 ≤ n ≤ 1000) — the number of values of the banknotes that used in Geraldion.

The second line contains n distinct space-separated numbers a1, a2, ..., an (1 ≤ ai ≤ 106) — the values of the banknotes.

## Output Format
Print a single line — the minimum unfortunate sum. If there are no unfortunate sums, print  - 1.

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

# Problem
Meg the Rabbit decided to do something nice, specifically — to determine the shortest distance between two points on the surface of our planet. But Meg... what can you say, she wants everything simple. So, she already regards our planet as a two-dimensional circle. No, wait, it's even worse — as a square of side n. Thus, the task has been reduced to finding the shortest path between two dots on a square (the path should go through the square sides). To simplify the task let us consider the vertices of the square to lie at points whose coordinates are: (0, 0), (n, 0), (0, n) and (n, n).

## Input Format
The single line contains 5 space-separated integers: n, x1, y1, x2, y2 (1 ≤ n ≤ 1000, 0 ≤ x1, y1, x2, y2 ≤ n) which correspondingly represent a side of the square, the coordinates of the first point and the coordinates of the second point. It is guaranteed that the points lie on the sides of the square.

## Output Format
You must print on a single line the shortest distance between the points.

## Examples
```input
2 0 0 1 0
```
```output
1
```
-----
```input
2 0 1 2 1
```
```output
4
```
-----
```input
100 0 0 100 100
```
```output
200
```

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
Chris the Rabbit has been interested in arrays ever since he was a child. At the moment he is researching arrays with the length of n, containing only integers from 1 to n. He is not good at math, that's why some simple things drive him crazy. For example, yesterday he grew keen on counting how many different beautiful arrays there are. Chris thinks that an array is beautiful if it meets one of the two conditions:

- each elements, starting from the second one, is no more than the preceding one
- each element, starting from the second one, is no less than the preceding one

Having got absolutely mad at himself and at math, Chris came to Stewie and Brian to ask them for help. However, they only laughed at him and said that the answer is too simple and not interesting. Help Chris the Rabbit to find the answer at last.

## Input Format
The single line contains an integer n which is the size of the array (1 ≤ n ≤ 105).

## Output Format
You must print the answer on a single line. As it can be rather long, you should print it modulo 1000000007.

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

Now solve the problem and return the code.