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

# Problem
Fox Ciel is in the Amusement Park. And now she is in a queue in front of the Ferris wheel. There are n people (or foxes more precisely) in the queue: we use first people to refer one at the head of the queue, and n-th people to refer the last one in the queue.

There will be k gondolas, and the way we allocate gondolas looks like this:

- When the first gondolas come, the q1 people in head of the queue go into the gondolas.
- Then when the second gondolas come, the q2 people in head of the remain queue go into the gondolas.    ...
- The remain qk people go into the last (k-th) gondolas.

Note that q1, q2, ..., qk must be positive. You can get from the statement that $$\sum_{i=1}^{k} q_i = n$$ and qi > 0.

You know, people don't want to stay with strangers in the gondolas, so your task is to find an optimal allocation way (that is find an optimal sequence q) to make people happy. For every pair of people i and j, there exists a value uij denotes a level of unfamiliar. You can assume uij = uji for all i, j (1 ≤ i, j ≤ n) and uii = 0 for all i (1 ≤ i ≤ n). Then an unfamiliar value of a gondolas is the sum of the levels of unfamiliar between any pair of people that is into the gondolas.

A total unfamiliar value is the sum of unfamiliar values for all gondolas. Help Fox Ciel to find the minimal possible total unfamiliar value for some optimal allocation.

## Input Format
The first line contains two integers n and k (1 ≤ n ≤ 4000 and 1 ≤ k ≤ min(n, 800)) — the number of people in the queue and the number of gondolas. Each of the following n lines contains n integers — matrix u, (0 ≤ uij ≤ 9, uij = uji and uii = 0).

Please, use fast input methods (for example, please use BufferedReader instead of Scanner for Java).

## Output Format
Print an integer — the minimal possible total unfamiliar value.

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

## Note
In the first example, we can allocate people like this: {1, 2} goes into a gondolas, {3, 4, 5} goes into another gondolas.

In the second example, an optimal solution is : {1, 2, 3} | {4, 5, 6} | {7, 8}.

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 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 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
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 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
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 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
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 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
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 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 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 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
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.
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 want to arrange n integers a1, a2, ..., an in some order in a row. Let's define the value of an arrangement as the sum of differences between all pairs of adjacent integers.

More formally, let's denote some arrangement as a sequence of integers x1, x2, ..., xn, where sequence x is a permutation of sequence a. The value of such an arrangement is (x1 - x2) + (x2 - x3) + ... + (xn - 1 - xn).

Find the largest possible value of an arrangement. Then, output the lexicographically smallest sequence x that corresponds to an arrangement of the largest possible value.

## Input Format
The first line of the input contains integer n (2 ≤ n ≤ 100). The second line contains n space-separated integers a1, a2, ..., an (|ai| ≤ 1000).

## Output Format
Print the required sequence x1, x2, ..., xn. Sequence x should be the lexicographically smallest permutation of a that corresponds to an arrangement of the largest possible value.

## Examples
```input
5
100 -100 50 0 -50
```
```output
100 -50 0 50 -100
```

## Note
In the sample test case, the value of the output arrangement is (100 - ( - 50)) + (( - 50) - 0) + (0 - 50) + (50 - ( - 100)) = 200. No other arrangement has a larger value, and among all arrangements with the value of 200, the output arrangement is the lexicographically smallest one.

Sequence x1, x2, ... , xp is lexicographically smaller than sequence y1, y2, ... , yp if there exists an integer r (0 ≤ r < p) such that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 < yr + 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 permutation of length n is an integer sequence such that each integer from 0 to (n - 1) appears exactly once in it. For example, sequence [0, 2, 1] is a permutation of length 3 while both [0, 2, 2] and [1, 2, 3] are not.

A fixed point of a function is a point that is mapped to itself by the function. A permutation can be regarded as a bijective function. We'll get a definition of a fixed point in a permutation. An integer i is a fixed point of permutation a0, a1, ..., an - 1 if and only if ai = i. For example, permutation [0, 2, 1] has 1 fixed point and permutation [0, 1, 2] has 3 fixed points.

You are given permutation a. You are allowed to swap two elements of the permutation at most once. Your task is to maximize the number of fixed points in the resulting permutation. Note that you are allowed to make at most one swap operation.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 105). The second line contains n integers a0, a1, ..., an - 1 — the given permutation.

## Output Format
Print a single integer — the maximum possible number of fixed points in the permutation after at most one swap operation.

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

Now solve the problem and return the code.