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

# Problem
Sereja placed n points on a plane. Now Sereja wants to place on the plane two straight lines, intersecting at a right angle, so that one of the straight lines intersect the Ox axis at an angle of 45 degrees and the maximum distance from the points to the straight lines were minimum.

In this problem we consider the distance between points (x1, y1) and (x2, y2) equal |x1 - x2| + |y1 - y2|. The distance between the point and the straight lines is the minimum distance from the point to some point belonging to one of the lines.

Help Sereja, find the maximum distance from the points to the optimally located straight lines.

## Input Format
The first line contains integer n (1 ≤ n ≤ 105). Next n lines contain the coordinates of the lines. The i-th line contains two integers xi, yi (|xi|, |yi| ≤ 109).

## Output Format
In a single line print a real number — the answer to the problem. Your answer will be considered correct iff its absolute or relative error doesn't exceed 10 - 6.

## Examples
```input
4
0 0
2 0
0 2
2 2
```
```output
0.000000000000000
```
-----
```input
4
1 0
0 1
2 1
1 2
```
```output
1.000000000000000
```

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

# Problem
Sereja painted n points on the plane, point number i (1 ≤ i ≤ n) has coordinates (i, 0). Then Sereja marked each point with a small or large English letter. Sereja don't like letter "x", so he didn't use it to mark points. Sereja thinks that the points are marked beautifully if the following conditions holds:

- all points can be divided into pairs so that each point will belong to exactly one pair;
- in each pair the point with the lesser abscissa will be marked with a small English letter and the point with the larger abscissa will be marked with the same large English letter;
- if we built a square on each pair, the pair's points will be the square's opposite points and the segment between them will be the square's diagonal, then among the resulting squares there won't be any intersecting or touching ones.

Little Petya erased some small and all large letters marking the points. Now Sereja wonders how many ways are there to return the removed letters so that the points were marked beautifully.

## Input Format
The first line contains integer n the number of points (1 ≤ n ≤ 105). The second line contains a sequence consisting of n small English letters and question marks — the sequence of letters, that mark points, in order of increasing x-coordinate of points. Question marks denote the points without letters (Petya erased them). It is guaranteed that the input string doesn't contain letter "x".

## Output Format
In a single line print the answer to the problem modulo 4294967296. If there is no way to return the removed letters, print number 0.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

## Examples
```input
4
a???
```
```output
50
```
-----
```input
4
abc?
```
```output
0
```
-----
```input
6
abc???
```
```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 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
A magic number is a number formed by concatenation of numbers 1, 14 and 144. We can use each of these numbers any number of times. Therefore 14144, 141414 and 1411 are magic numbers but 1444, 514 and 414 are not.

You're given a number. Determine if it is a magic number or not.

## Input Format
The first line of input contains an integer n, (1 ≤ n ≤ 109). This number doesn't contain leading zeros.

## Output Format
Print "YES" if n is a magic number or print "NO" if it's not.

## Examples
```input
114114
```
```output
YES
```
-----
```input
1111
```
```output
YES
```
-----
```input
441231
```
```output
NO
```

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
You are given n rectangles. The corners of rectangles have integer coordinates and their edges are parallel to the Ox and Oy axes. The rectangles may touch each other, but they do not overlap (that is, there are no points that belong to the interior of more than one rectangle).

Your task is to determine if the rectangles form a square. In other words, determine if the set of points inside or on the border of at least one rectangle is precisely equal to the set of points inside or on the border of some square.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 5). Next n lines contain four integers each, describing a single rectangle: x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 31400, 0 ≤ y1 < y2 ≤ 31400) — x1 and x2 are x-coordinates of the left and right edges of the rectangle, and y1 and y2 are y-coordinates of the bottom and top edges of the rectangle.

No two rectangles overlap (that is, there are no points that belong to the interior of more than one rectangle).

## Output Format
In a single line print "YES", if the given rectangles form a square, or "NO" otherwise.

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

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
Piegirl has found a monster and a book about monsters and pies. When she is reading the book, she found out that there are n types of monsters, each with an ID between 1 and n. If you feed a pie to a monster, the monster will split into some number of monsters (possibly zero), and at least one colorful diamond. Monsters may be able to split in multiple ways.

At the begining Piegirl has exactly one monster. She begins by feeding the monster a pie. She continues feeding pies to monsters until no more monsters are left. Then she collects all the diamonds that were created.

You will be given a list of split rules describing the way in which the various monsters can split. Every monster can split in at least one way, and if a monster can split in multiple ways then each time when it splits Piegirl can choose the way it splits.

For each monster, determine the smallest and the largest number of diamonds Piegirl can possibly collect, if initially she has a single instance of that monster. Piegirl has an unlimited supply of pies.

## Input Format
The first line contains two integers: m and n (1 ≤ m, n ≤ 105), the number of possible splits and the number of different monster types. Each of the following m lines contains a split rule. Each split rule starts with an integer (a monster ID) mi (1 ≤ mi ≤ n), and a positive integer li indicating the number of monsters and diamonds the current monster can split into. This is followed by li integers, with positive integers representing a monster ID and -1 representing a diamond.

Each monster will have at least one split rule. Each split rule will have at least one diamond. The sum of li across all split rules will be at most 105.

## Output Format
For each monster, in order of their IDs, print a line with two integers: the smallest and the largest number of diamonds that can possibly be collected by starting with that monster. If Piegirl cannot possibly end up in a state without monsters, print -1 for both smallest and the largest value. If she can collect an arbitrarily large number of diamonds, print -2 as the largest number of diamonds.

If any number in output exceeds 314000000 (but is finite), print 314000000 instead of that number.

## Examples
```input
6 4
1 3 -1 1 -1
1 2 -1 -1
2 3 -1 3 -1
2 3 -1 -1 -1
3 2 -1 -1
4 2 4 -1
```
```output
2 -2
3 4
2 2
-1 -1
```
-----
```input
3 2
1 2 1 -1
2 2 -1 -1
2 3 2 1 -1
```
```output
-1 -1
2 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 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
Piegirl found the red button. You have one last chance to change the inevitable end.

The circuit under the button consists of n nodes, numbered from 0 to n - 1. In order to deactivate the button, the n nodes must be disarmed in a particular order. Node 0 must be disarmed first. After disarming node i, the next node to be disarmed must be either node (2·i) modulo n or node (2·i) + 1 modulo n. The last node to be disarmed must be node 0. Node 0 must be disarmed twice, but all other nodes must be disarmed exactly once.

Your task is to find any such order and print it. If there is no such order, print -1.

## Input Format
Input consists of a single integer n (2 ≤ n ≤ 105).

## Output Format
Print an order in which you can to disarm all nodes. If it is impossible, print -1 instead. If there are multiple orders, print any one of them.

## Examples
```input
2
```
```output
0 1 0
```
-----
```input
3
```
```output
-1
```
-----
```input
4
```
```output
0 1 3 2 0
```
-----
```input
16
```
```output
0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 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 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
Consider a table G of size n × m such that G(i, j) = GCD(i, j) for all 1 ≤ i ≤ n, 1 ≤ j ≤ m. GCD(a, b) is the greatest common divisor of numbers a and b.

You have a sequence of positive integer numbers a1, a2, ..., ak. We say that this sequence occurs in table G if it coincides with consecutive elements in some row, starting from some position. More formally, such numbers 1 ≤ i ≤ n and 1 ≤ j ≤ m - k + 1 should exist that G(i, j + l - 1) = al for all 1 ≤ l ≤ k.

Determine if the sequence a occurs in table G.

## Input Format
The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 1012; 1 ≤ k ≤ 10000). The second line contains k space-separated integers a1, a2, ..., ak (1 ≤ ai ≤ 1012).

## Output Format
Print a single word "YES", if the given sequence occurs in table G, otherwise print "NO".

## Examples
```input
100 100 5
5 2 1 2 1
```
```output
YES
```
-----
```input
100 8 5
5 2 1 2 1
```
```output
NO
```
-----
```input
100 100 7
1 2 3 4 5 6 7
```
```output
NO
```

## Note
Sample 1. The tenth row of table G starts from sequence {1, 2, 1, 2, 5, 2, 1, 2, 1, 10}. As you can see, elements from fifth to ninth coincide with sequence a.

Sample 2. This time the width of table G equals 8. Sequence a doesn't occur there.

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
Xenia the mathematician has a sequence consisting of n (n is divisible by 3) positive integers, each of them is at most 7. She wants to split the sequence into groups of three so that for each group of three a, b, c the following conditions held:

- a < b < c;
- a divides b, b divides c.

Naturally, Xenia wants each element of the sequence to belong to exactly one group of three. Thus, if the required partition exists, then it has $$\frac{\pi}{3}$$ groups of three.

Help Xenia, find the required partition or else say that it doesn't exist.

## Input Format
The first line contains integer n (3 ≤ n ≤ 99999) — the number of elements in the sequence. The next line contains n positive integers, each of them is at most 7.

It is guaranteed that n is divisible by 3.

## Output Format
If the required partition exists, print $$\frac{\pi}{3}$$ groups of three. Print each group as values of the elements it contains. You should print values in increasing order. Separate the groups and integers in groups by whitespaces. If there are multiple solutions, you can print any of them.

If there is no solution, print -1.

## Examples
```input
6
1 1 1 2 2 2
```
```output
-1
```
-----
```input
6
2 2 1 1 4 6
```
```output
1 2 4
1 2 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 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
Xenia the vigorous detective faced n (n ≥ 2) foreign spies lined up in a row. We'll consider the spies numbered from 1 to n from left to right.

Spy s has an important note. He has to pass the note to spy f. Xenia interrogates the spies in several steps. During one step the spy keeping the important note can pass the note to one of his neighbours in the row. In other words, if this spy's number is x, he can pass the note to another spy, either x - 1 or x + 1 (if x = 1 or x = n, then the spy has only one neighbour). Also during a step the spy can keep a note and not pass it to anyone.

But nothing is that easy. During m steps Xenia watches some spies attentively. Specifically, during step ti (steps are numbered from 1) Xenia watches spies numbers li, li + 1, li + 2, ..., ri (1 ≤ li ≤ ri ≤ n). Of course, if during some step a spy is watched, he can't do anything: neither give the note nor take it from some other spy. Otherwise, Xenia reveals the spies' cunning plot. Nevertheless, if the spy at the current step keeps the note, Xenia sees nothing suspicious even if she watches him.

You've got s and f. Also, you have the steps during which Xenia watches spies and which spies she is going to watch during each step. Find the best way the spies should act in order to pass the note from spy s to spy f as quickly as possible (in the minimum number of steps).

## Input Format
The first line contains four integers n, m, s and f (1 ≤ n, m ≤ 105; 1 ≤ s, f ≤ n; s ≠ f; n ≥ 2). Each of the following m lines contains three integers ti, li, ri (1 ≤ ti ≤ 109, 1 ≤ li ≤ ri ≤ n). It is guaranteed that t1 < t2 < t3 < ... < tm.

## Output Format
Print k characters in a line: the i-th character in the line must represent the spies' actions on step i. If on step i the spy with the note must pass the note to the spy with a lesser number, the i-th character should equal "L". If on step i the spy with the note must pass it to the spy with a larger number, the i-th character must equal "R". If the spy must keep the note at the i-th step, the i-th character must equal "X".

As a result of applying the printed sequence of actions spy s must pass the note to spy f. The number of printed characters k must be as small as possible. Xenia must not catch the spies passing the note.

If there are miltiple optimal solutions, you can print any of them. It is guaranteed that the answer exists.

## Examples
```input
3 5 1 3
1 1 2
2 2 3
3 3 3
4 1 1
10 1 3
```
```output
XXRR
```

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
A girl named Xenia has a cupboard that looks like an arc from ahead. The arc is made of a semicircle with radius r (the cupboard's top) and two walls of height h (the cupboard's sides). The cupboard's depth is r, that is, it looks like a rectangle with base r and height h + r from the sides. The figure below shows what the cupboard looks like (the front view is on the left, the side view is on the right).

Xenia got lots of balloons for her birthday. The girl hates the mess, so she wants to store the balloons in the cupboard. Luckily, each balloon is a sphere with radius $$\frac{7}{2}$$. Help Xenia calculate the maximum number of balloons she can put in her cupboard.

You can say that a balloon is in the cupboard if you can't see any part of the balloon on the left or right view. The balloons in the cupboard can touch each other. It is not allowed to squeeze the balloons or deform them in any way. You can assume that the cupboard's walls are negligibly thin.

## Input Format
The single line contains two integers r, h (1 ≤ r, h ≤ 107).

## Output Format
Print a single integer — the maximum number of balloons Xenia can put in the cupboard.

## Examples
```input
1 1
```
```output
3
```
-----
```input
1 2
```
```output
5
```
-----
```input
2 1
```
```output
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 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
Xenia likes puzzles very much. She is especially fond of the puzzles that consist of domino pieces. Look at the picture that shows one of such puzzles.

A puzzle is a 3 × n table with forbidden cells (black squares) containing dominoes (colored rectangles on the picture). A puzzle is called correct if it meets the following conditions:

- each domino occupies exactly two non-forbidden cells of the table;
- no two dominoes occupy the same table cell;
- exactly one non-forbidden cell of the table is unoccupied by any domino (it is marked by a circle in the picture).

To solve the puzzle, you need multiple steps to transport an empty cell from the starting position to some specified position. A move is transporting a domino to the empty cell, provided that the puzzle stays correct. The horizontal dominoes can be moved only horizontally, and vertical dominoes can be moved only vertically. You can't rotate dominoes. The picture shows a probable move.

Xenia has a 3 × n table with forbidden cells and a cell marked with a circle. Also, Xenia has very many identical dominoes. Now Xenia is wondering, how many distinct correct puzzles she can make if she puts dominoes on the existing table. Also, Xenia wants the circle-marked cell to be empty in the resulting puzzle. The puzzle must contain at least one move.

Help Xenia, count the described number of puzzles. As the described number can be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

## Input Format
The first line contains integer n (3 ≤ n ≤ 104) — the puzzle's size. Each of the following three lines contains n characters — the description of the table. The j-th character of the i-th line equals "X" if the corresponding cell is forbidden; it equals ".", if the corresponding cell is non-forbidden and "O", if the corresponding cell is marked with a circle.

It is guaranteed that exactly one cell in the table is marked with a circle. It is guaranteed that all cells of a given table having at least one common point with the marked cell is non-forbidden.

## Output Format
Print a single number — the answer to the problem modulo 1000000007 (109 + 7).

## Examples
```input
5
....X
.O...
...X.
```
```output
1
```
-----
```input
5
.....
.O...
.....
```
```output
2
```
-----
```input
3
...
...
..O
```
```output
4
```

## Note
Two puzzles are considered distinct if there is a pair of cells that contain one domino in one puzzle and do not contain it in the other one.

Now solve the problem and return the code.