apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given n points on the straight line — the positions (x-coordinates) of the cities and m points on the same line — the positions (x-coordinates) of the cellular towers. All towers work in the same way — they provide cellular network for all cities, which are located at the distance which is no more than r from this tower.

Your task is to find minimal r that each city has been provided by cellular network, i.e. for each city there is at least one cellular tower at the distance which is no more than r.

If r = 0 then a tower provides cellular network only for the point where it is located. One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than r from this tower.

## Input Format
The first line contains two positive integers n and m (1 ≤ n, m ≤ 105) — the number of cities and the number of cellular towers.

The second line contains a sequence of n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the coordinates of cities. It is allowed that there are any number of cities in the same point. All coordinates ai are given in non-decreasing order.

The third line contains a sequence of m integers b1, b2, ..., bm ( - 109 ≤ bj ≤ 109) — the coordinates of cellular towers. It is allowed that there are any number of towers in the same point. All coordinates bj are given in non-decreasing order.

## Output Format
Print minimal r so that each city will be covered by cellular network.

## Examples
```input
3 2
-2 2 4
-3 0
```
```output
4
```
-----
```input
5 3
1 5 10 14 17
4 11 15
```
```output
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 c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vasiliy has a car and he wants to get from home to the post office. The distance which he needs to pass equals to d kilometers.

Vasiliy's car is not new — it breaks after driven every k kilometers and Vasiliy needs t seconds to repair it. After repairing his car Vasiliy can drive again (but after k kilometers it will break again, and so on). In the beginning of the trip the car is just from repair station.

To drive one kilometer on car Vasiliy spends a seconds, to walk one kilometer on foot he needs b seconds (a < b).

Your task is to find minimal time after which Vasiliy will be able to reach the post office. Consider that in every moment of time Vasiliy can left his car and start to go on foot.

## Input Format
The first line contains 5 positive integers d, k, a, b, t (1 ≤ d ≤ 1012; 1 ≤ k, a, b, t ≤ 106; a < b), where:

- d — the distance from home to the post office;
- k — the distance, which car is able to drive before breaking;
- a — the time, which Vasiliy spends to drive 1 kilometer on his car;
- b — the time, which Vasiliy spends to walk 1 kilometer on foot;
- t — the time, which Vasiliy spends to repair his car.

## Output Format
Print the minimal time after which Vasiliy will be able to reach the post office.

## Examples
```input
5 2 1 4 10
```
```output
14
```
-----
```input
5 2 1 4 5
```
```output
13
```

## Note
In the first example Vasiliy needs to drive the first 2 kilometers on the car (in 2 seconds) and then to walk on foot 3 kilometers (in 12 seconds). So the answer equals to 14 seconds.

In the second example Vasiliy needs to drive the first 2 kilometers on the car (in 2 seconds), then repair his car (in 5 seconds) and drive 2 kilometers more on the car (in 2 seconds). After that he needs to walk on foot 1 kilometer (in 4 seconds). So the answer equals to 13 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 c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a functional graph. It is a directed graph, in which from each vertex goes exactly one arc. The vertices are numerated from 0 to n - 1.

Graph is given as the array f0, f1, ..., fn - 1, where fi — the number of vertex to which goes the only arc from the vertex i. Besides you are given array with weights of the arcs w0, w1, ..., wn - 1, where wi — the arc weight from i to fi.

The graph from the first sample test.

Also you are given the integer k (the length of the path) and you need to find for each vertex two numbers si and mi, where:

- si — the sum of the weights of all arcs of the path with length equals to k which starts from the vertex i;
- mi — the minimal weight from all arcs on the path with length k which starts from the vertex i.

The length of the path is the number of arcs on this path.

## Input Format
The first line contains two integers n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1010). The second line contains the sequence f0, f1, ..., fn - 1 (0 ≤ fi < n) and the third — the sequence w0, w1, ..., wn - 1 (0 ≤ wi ≤ 108).

## Output Format
Print n lines, the pair of integers si, mi in each line.

## Examples
```input
7 3
1 2 3 4 3 2 6
6 3 1 4 2 2 3
```
```output
10 1
8 1
7 1
10 2
8 2
7 1
9 3
```
-----
```input
4 4
0 1 2 3
0 1 2 3
```
```output
0 0
4 1
8 2
12 3
```
-----
```input
5 3
1 2 3 4 0
4 1 2 14 3
```
```output
7 1
17 1
19 2
21 3
8 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 c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Alex studied well and won the trip to student camp Alushta, located on the seashore.

Unfortunately, it's the period of the strong winds now and there is a chance the camp will be destroyed! Camp building can be represented as the rectangle of n + 2 concrete blocks height and m blocks width.

Every day there is a breeze blowing from the sea. Each block, except for the blocks of the upper and lower levers, such that there is no block to the left of it is destroyed with the probability $$p = \frac{a}{b}$$. Similarly, each night the breeze blows in the direction to the sea. Thus, each block (again, except for the blocks of the upper and lower levers) such that there is no block to the right of it is destroyed with the same probability p. Note, that blocks of the upper and lower level are indestructible, so there are only n·m blocks that can be destroyed.

The period of the strong winds will last for k days and k nights. If during this period the building will split in at least two connected components, it will collapse and Alex will have to find another place to spend summer.

Find the probability that Alex won't have to look for other opportunities and will be able to spend the summer in this camp.

## Input Format
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 1500) that define the size of the destructible part of building.

The second line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 109) that define the probability p. It's guaranteed that integers a and b are coprime.

The third line contains a single integer k (0 ≤ k ≤ 100 000) — the number of days and nights strong wind will blow for.

## Output Format
Consider the answer as an irreducible fraction is equal to $$\frac{c}{d}$$. Print one integer equal to $$c \cdot d^{-1} \mod 10^{9} + 7$$. It's guaranteed that within the given constraints $$d \neq 0 \pmod{10^9 + 7}$$.

## Examples
```input
2 2
1 2
1
```
```output
937500007
```
-----
```input
5 1
3 10
1
```
```output
95964640
```
-----
```input
3 3
1 10
5
```
```output
927188454
```

## Note
In the first sample, each of the four blocks is destroyed with the probability $$\frac{1}{2}$$. There are 7 scenarios that result in building not collapsing, and the probability we are looking for is equal to $$\frac{7}{16}$$, so you should print $$7 \cdot 16^{-1} = 7 \cdot 562500004 = 937500007 \pmod {10^9 + 7}$$

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Today an outstanding event is going to happen in the forest — hedgehog Filya will come to his old fried Sonya!

Sonya is an owl and she sleeps during the day and stay awake from minute l1 to minute r1 inclusive. Also, during the minute k she prinks and is unavailable for Filya.

Filya works a lot and he plans to visit Sonya from minute l2 to minute r2 inclusive.

Calculate the number of minutes they will be able to spend together.

## Input Format
The only line of the input contains integers l1, r1, l2, r2 and k (1 ≤ l1, r1, l2, r2, k ≤ 1018, l1 ≤ r1, l2 ≤ r2), providing the segments of time for Sonya and Filya and the moment of time when Sonya prinks.

## Output Format
Print one integer — the number of minutes Sonya and Filya will be able to spend together.

## Examples
```input
1 10 9 20 1
```
```output
2
```
-----
```input
1 100 50 200 75
```
```output
50
```

## Note
In the first sample, they will be together during minutes 9 and 10.

In the second sample, they will be together from minute 50 to minute 74 and from minute 76 to minute 100.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Today, hedgehog Filya went to school for the very first time! Teacher gave him a homework which Filya was unable to complete without your help.

Filya is given an array of non-negative integers a1, a2, ..., an. First, he pick an integer x and then he adds x to some elements of the array (no more than once), subtract x from some other elements (also, no more than once) and do no change other elements. He wants all elements of the array to be equal.

Now he wonders if it's possible to pick such integer x and change some elements of the array using this x in order to make all elements equal.

## Input Format
The first line of the input contains an integer n (1 ≤ n ≤ 100 000) — the number of integers in the Filya's array. The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109) — elements of the array.

## Output Format
If it's impossible to make all elements of the array equal using the process given in the problem statement, then print "NO" (without quotes) in the only line of the output. Otherwise print "YES" (without quotes).

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

## Note
In the first sample Filya should select x = 1, then add it to the first and the last elements of the array and subtract from the second and the third elements.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
In a new version of the famous Pinball game, one of the most important parts of the game field is a sequence of n bumpers. The bumpers are numbered with integers from 1 to n from left to right. There are two types of bumpers. They are denoted by the characters '<' and '>'. When the ball hits the bumper at position i it goes one position to the right (to the position i + 1) if the type of this bumper is '>', or one position to the left (to i - 1) if the type of the bumper at position i is '<'. If there is no such position, in other words if i - 1 < 1 or i + 1 > n, the ball falls from the game field.

Depending on the ball's starting position, the ball may eventually fall from the game field or it may stay there forever. You are given a string representing the bumpers' types. Calculate the number of positions such that the ball will eventually fall from the game field if it starts at that position.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the sequence of bumpers. The second line contains the string, which consists of the characters '<' and '>'. The character at the i-th position of this string corresponds to the type of the i-th bumper.

## Output Format
Print one integer — the number of positions in the sequence such that the ball will eventually fall from the game field if it starts at that position.

## Examples
```input
4
<<><
```
```output
2
```
-----
```input
5
>>>>>
```
```output
5
```
-----
```input
4
>><<
```
```output
0
```

## Note
In the first sample, the ball will fall from the field if starts at position 1 or position 2.

In the second sample, any starting position will result in the ball falling from the field.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let’s define a grid to be a set of tiles with 2 rows and 13 columns. Each tile has an English letter written in it. The letters don't have to be unique: there might be two or more tiles with the same letter written on them. Here is an example of a grid:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

We say that two tiles are adjacent if they share a side or a corner. In the example grid above, the tile with the letter 'A' is adjacent only to the tiles with letters 'B', 'N', and 'O'. A tile is not adjacent to itself.

A sequence of tiles is called a path if each tile in the sequence is adjacent to the tile which follows it (except for the last tile in the sequence, which of course has no successor). In this example, "ABC" is a path, and so is "KXWIHIJK". "MAB" is not a path because 'M' is not adjacent to 'A'. A single tile can be used more than once by a path (though the tile cannot occupy two consecutive places in the path because no tile is adjacent to itself).

You’re given a string s which consists of 27 upper-case English letters. Each English letter occurs at least once in s. Find a grid that contains a path whose tiles, viewed in the order that the path visits them, form the string s. If there’s no solution, print "Impossible" (without the quotes).

## Input Format
The only line of the input contains the string s, consisting of 27 upper-case English letters. Each English letter occurs at least once in s.

## Output Format
Output two lines, each consisting of 13 upper-case English characters, representing the rows of the grid. If there are multiple solutions, print any of them. If there is no solution print "Impossible".

## Examples
```input
ABCDEFGHIJKLMNOPQRSGTUVWXYZ
```
```output
YXWVUTGHIJKLM
ZABCDEFSRQPON
```
-----
```input
BUVTYZFQSNRIWOXXGJLKACPEMDH
```
```output
Impossible
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Alice and Bonnie are sisters, but they don't like each other very much. So when some old family photos were found in the attic, they started to argue about who should receive which photos. In the end, they decided that they would take turns picking photos. Alice goes first.

There are n stacks of photos. Each stack contains exactly two photos. In each turn, a player may take only a photo from the top of one of the stacks.

Each photo is described by two non-negative integers a and b, indicating that it is worth a units of happiness to Alice and b units of happiness to Bonnie. Values of a and b might differ for different photos.

It's allowed to pass instead of taking a photo. The game ends when all photos are taken or both players pass consecutively.

The players don't act to maximize their own happiness. Instead, each player acts to maximize the amount by which her happiness exceeds her sister's. Assuming both players play optimal, find the difference between Alice's and Bonnie's happiness. That is, if there's a perfectly-played game such that Alice has x happiness and Bonnie has y happiness at the end, you should print x - y.

## Input Format
The first line of input contains a single integer n (1 ≤ n ≤ 100 000) — the number of two-photo stacks. Then follow n lines, each describing one of the stacks. A stack is described by four space-separated non-negative integers a1, b1, a2 and b2, each not exceeding 109. a1 and b1 describe the top photo in the stack, while a2 and b2 describe the bottom photo in the stack.

## Output Format
Output a single integer: the difference between Alice's and Bonnie's happiness if both play optimally.

## Examples
```input
2
12 3 4 7
1 15 9 1
```
```output
1
```
-----
```input
2
5 4 8 8
4 12 14 0
```
```output
4
```
-----
```input
1
0 10 0 10
```
```output
-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 c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
One day, the Grasshopper was jumping on the lawn and found a piece of paper with a string. Grasshopper became interested what is the minimum jump ability he should have in order to be able to reach the far end of the string, jumping only on vowels of the English alphabet. Jump ability is the maximum possible length of his jump.

Formally, consider that at the begginning the Grasshopper is located directly in front of the leftmost character of the string. His goal is to reach the position right after the rightmost character of the string. In one jump the Grasshopper could jump to the right any distance from 1 to the value of his jump ability.

The picture corresponds to the first example.

The following letters are vowels: 'A', 'E', 'I', 'O', 'U' and 'Y'.

## Input Format
The first line contains non-empty string consisting of capital English letters. It is guaranteed that the length of the string does not exceed 100.

## Output Format
Print single integer a — the minimum jump ability of the Grasshopper (in the number of symbols) that is needed to overcome the given string, jumping only on vowels.

## Examples
```input
ABABBBACFEYUKOTT
```
```output
4
```
-----
```input
AAA
```
```output
1
```

Now solve the problem and return the code.