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

# Problem
You are given two sets of numbers. Your task is to print all numbers from the sets, that both sets don't contain simultaneously.

## Input Format
The first line contains the description of the first set, the second line contains the description of the second set. Each description begins with the number of elements in this set. All elements of the set follow in the arbitrary order. In each set all elements are distinct and both sets are not empty. The number of elements in each set doesn't exceed 1000. All elements of the sets are integers from -1000 to 1000.

## Output Format
Print the number of the required numbers and then the numbers themselves separated by a space.

## Examples
```input
3 1 2 3
3 2 3 4
```
```output
2 1 4
```
-----
```input
5 1 4 8 9 10
4 1 2 8 10
```
```output
3 2 4 9
```

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
A chocolate bar has a rectangular shape and consists of n × m slices. In other words, a bar consists of n rows with m slices of chocolate in each row.

Each slice of chocolate is known to weigh 1 gram. Your task is to determine for each of the q chocolate bars whether it is possible to obtain a piece weighing p grams by breaking the bar several (possibly zero) times. The final piece of the chocolate bar should be whole, and breaks are made along the line of slices' section for the whole length of the current piece.

## Input Format
The first line contains the positive integer q (1 ≤ q ≤ 100) — the number of chocolate bars.

Each of the following q lines contains three positive integers n, m and p (1 ≤ n, m, p ≤ 1000) — the size of the chocolate bar, and the weight of the piece which should be obtained.

## Output Format
The output should contain q lines and the i-th line must contain "Yes" (without the quotes), if it is possible to perform the task for i-th chocolate bar, or "No" otherwise.

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

# Problem
n athletes take part in the hammer throw. Each of them has his own unique identifier — the integer from 1 to n (all athletes have distinct identifiers). After the draw, the order in which the athletes will throw the hammer has been determined (they will do it one by one).

Unfortunately, a not very attentive judge lost the list with the order of athletes, but each of the athletes has remembered how many competitors with identifiers larger than his own will throw the hammer before him.

Your task is to help the organizers as quickly as possible to restore the order of the athletes.

## Input Format
The first line contains the positive integer n (1 ≤ n ≤ 1000) — the number of athletes.

The next line contains the sequence of integers a1, a2, ..., an (0 ≤ ai < n), where ai is equal to the number of the athletes with identifiers larger than i, who should throw the hammer before the athlete with identifier i.

## Output Format
Print n distinct numbers — the sequence of athletes' identifiers in the order in which they will throw the hammer. If there are several answers it is allowed to print any of them.

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

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
In this problem you are given a string s consisting of uppercase and lowercase Latin letters, spaces, dots and commas. Your task is to correct the formatting of this string by removing and inserting spaces, as well as changing the case of the letters.

After formatting, the resulting string must meet the following requirements:

- the string must not start with a space;
- there should be exactly one space between any two consecutive words;
- there should be a Latin letter immediately before a dot or a comma, and there should be a space immediately after a dot or a comma in the case that there is a word after that dot or comma, otherwise that dot or comma must be the last character in the string;
- all letters must be lowercase, except all first letters in the first words of the sentences, they must be capitalized. The first word of a sentence is a word that is either the first word of the string or a word after a dot.

It is guaranteed that there is at least one letter in the given string between any two punctuation marks (commas and dots are punctuation marks). There is at least one letter before the leftmost punctuation mark.

## Input Format
The first line contains a non-empty string s, consisting of uppercase and lowercase Latin letters, spaces, dots and commas. The length of the given string does not exceed 255. The string is guaranteed to have at least one character other than the space.

## Output Format
Output the corrected string which meets all the requirements described in the statement.

## Examples
```input
hello ,i AM veRy GooD.Boris
```
```output
Hello, i am very good. Boris
```
-----
```input
a. b,   C  .
```
```output
A. B, c.
```

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
Periodic decimal fraction is usually written as: [entire_part.non-periodic_part (period)]. Any simple fraction can be represented as a periodic decimal fraction and vice versa. For example, the decimal fraction 0.2(45) corresponds to a fraction 27 / 110. Your task is to convert the periodic fraction to a simple periodic fraction.

## Input Format
The first line contains the periodic decimal fraction x (0 < x < 1) in the format described in the statement. The total number of digits in the period and non-periodic part of the fraction does not exceed 8. Non-periodic part may be absent, the periodic part can't be absent (but it can be equal to any non-negative number).

## Output Format
Print the representation of the fraction x as a simple fraction p / q, where p and q are mutually prime integers.

## Examples
```input
0.2(45)
```
```output
27/110
```
-----
```input
0.75(0)
```
```output
3/4
```

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
n pupils, who love to read books, study at school. It is known that each student has exactly one best friend, and each pupil is the best friend of exactly one other pupil. Each of the pupils has exactly one interesting book.

The pupils decided to share books with each other. Every day, all pupils give their own books to their best friends. Thus, every day each of the pupils has exactly one book.

Your task is to use the list of the best friends and determine the exchange of books among pupils after k days. For simplicity, all students are numbered from 1 to n in all tests.

## Input Format
The first line contains two integers n and k (2 ≤ n ≤ 100000, 1 ≤ k ≤ 1016) — the number of pupils and days during which they will exchange books.

The second line contains n different integers ai (1 ≤ ai ≤ n), where ai is equal to the number of the pupil who has the best friend with the number i.

It is guaranteed that no pupil is the best friend of himself.

## Output Format
In a single line print n different integers, where i-th integer should be equal to the number of the pupil who will have the book, which the pupil with the number i had in the beginning, after k days.

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

## Note
The explanation to the first test.

There are 4 pupils and 1 day. The list of the best friends equals to {2, 4, 1, 3}. It means that:

- the pupil with the number 3 — is the best friend of pupil with the number 1,
- the pupil with the number 1 — is the best friend of pupil with the number 2,
- the pupil with the number 4 — is the best friend of pupil with the number 3,
- the pupil with the number 2 — is the best friend of pupil with the number 4.

After the first day the exchange of books will be {3, 1, 4, 2}.

- the pupil with the number 3 will have the book, which the pupil with the number 1 had in the beginning,
- the pupil with the number 1 will have the book, which the pupil with the number 2 had in the beginning,
- the pupil with the number 4 will have the book, which the pupil with the number 3 had in the beginning
- the pupil with the number 2 will have the book, which the pupil with the number 4 had in the beginning.

Thus, the answer is 3 1 4 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
A loader works in a warehouse, which is a rectangular field with size n × m. Some cells of this field are free, others are occupied by pillars on which the roof of the warehouse rests.

There is a load in one of the free cells, and the loader in another. At any moment, the loader and the load can not be in the cells with columns, outside the warehouse or in the same cell.

The loader can move to the adjacent cell (two cells are considered adjacent if they have a common side), or move the load. To move the load, the loader should reach the cell adjacent to the load and push the load. In this case the load advances to the next cell in the direction in which the loader pushes it and the loader ends up in the cell in which the load was.

Your task is to determine a sequence of pushes and loader's movements after which the load will reach the given cell (it is guaranteed that this cell is free). The load is rather heavy, so you need to minimize first the number of pushes and second the number of loader's movements.

## Input Format
The first line contains two positive integers n and m (1 ≤ n, m ≤ 40, n·m ≥ 3) — the number of rows and columns in the rectangular field.

Each of the next n lines contains m characters — the description of the warehouse. If there is a character in the next cell of the warehouse:

- "X", it means, that the current cell contains the column;
- ".", it means, that the current cell is free;
- "Y", it means, that the loader is in the current cell;
- "B", it means, that the load is in the current cell;
- "T", it means, that the load should be moved to this cell.

It is guaranteed that there is exactly one load, one loader and one cell to which the load should be moved.

## Output Format
If the loader is not able to move the load to the given cell, print "NO" (without the quotes) in the first line of the output.

Otherwise, print "YES" (without the quotes) in the first line of the output, and in the second line — the sequence of characters that determines movements and pushes of the loader. Characters w, e, n, s shall denote loader's moves to the west, east, north and south, respectively. Characters W, E, N, S must denote loader's pushes in the corresponding directions. First of all you need to minimize the number of pushes of the load and second, the number of movements of the loader. If there are several answers, you are allowed to print any of them.

## Examples
```input
3 3
..Y
.BX
..T
```
```output
YES
wSwsE
```
-----
```input
3 3
.BY
...
TXX
```
```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
In a new computer game you need to help the hero to get out of the maze, which is a rectangular field of size n × m. The hero is located in one of the cells of this field. He knows where the exit of the maze is, and he wants to reach it.

In one move, the hero can either move to the next cell (i.e. the cell which has a common side with the current cell) if it is free, or plant a bomb on the cell where he is, or skip the move and do nothing. A planted bomb explodes after three moves, that is, after the hero makes 3 more actions but does not have time to make the fourth (all three types of moves described above are considered as actions).

The explosion destroys the obstacles in all the cells which have at least one common point with this cell (i.e. in all the cells sharing with the bomb cell a corner or a side). The explosion must not hurt the cell with the exit or the cell with the hero. The hero can not go beyond the boundaries of the maze.

Your task is to determine the sequence of hero's actions to reach the exit. Note that you haven't to minimize the length of the sequence. The only restriction — the length of the resulting sequence should not exceed 100,000 symbols.

## Input Format
The first line contains two integers n and m (1 ≤ n, m ≤ 100, n·m > 1) — sizes of the maze.

Each of the following n lines contains m characters — description of the maze. The character "." means a free cell, "E" — the hero, "T" — the exit, "X" — the obstacle.

It is guaranteed that there is exactly one hero and exactly one exit in the maze.

## Output Format
Print the hero's actions which will help him get out of the maze ("M" — to plant a bomb, "T" — to skip the move, "S" — to go down, "W" — to go left, "N" — to go up, "E" — to go right). If the hero can not reach the exit, print "No solution" (without quotes).

The length of the resulting sequence should not exceed 100,000 symbols. If there are several solutions it is allowed to print any of them.

## Examples
```input
3 5
XEX.X
X.XXT
X.X.X
```
```output
SSMNNTSSNEMWWTEEEE
```

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

# Problem
Owl Sonya decided to become a partymaker. To train for this role she gather all her owl friends in the country house. There are m chairs located in a circle and consequently numbered with integers from 1 to m. Thus, chairs i and i + 1 are neighbouring for all i from 1 to m - 1. Chairs 1 and m are also neighbouring. Some chairs are occupied by her friends. There are n friends in total. No two friends occupy the same chair. Rules are the following:

1. Each participant removes from the game the chair he is currently sitting on.
2. Each of the participants choose a direction that she will follow: clockwise (indices increase, from m goes to 1) and counter-clockwise (indices decrease, from 1 goes to m). This direction may coincide or be different for any pair of owls.
3. Each turn all guests move one step in the chosen directions. If some guest move to the position with a chair there, he removes this chair from the game.
4. Game ends if there are no more chairs left in the game.

Owls are very busy and want to get rid of the game as soon as possible. They cooperate to pick the direction. Your goal is to find the minimum number o moves required to finish the game.

## Input Format
The first line of the input contains a single integer m (1 ≤ m ≤ 109) — the length of the circle.

The second line contains a single integer n (1 ≤ n ≤ 100 000) — the number of friends.

Last line contains an increasing sequence of n integers ai (1 ≤ ai ≤ m) — initial positions of all owls.

## Output Format
Print the minimum number of move required to finish the game. Note, that 0 also may be an answer.

## Examples
```input
6
3
1 3 5
```
```output
1
```
-----
```input
6
2
1 6
```
```output
2
```
-----
```input
406
6
1 2 3 204 205 206
```
```output
100
```

## Note
In the first sample, it's possible if all owls will move clockwise, i.e. in the direction of increasing indices.

In the sample, first owl has to move clockwise, while the second — counterclockwise.

In the third sample, the first and the fourth owls should move counterclockwise, while the third and the sixth — clockwise. The second and the firth may move in any direction.

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
ZS the Coder is coding on a crazy computer. If you don't type in a word for a c consecutive seconds, everything you typed disappear!

More formally, if you typed a word at second a and then the next word at second b, then if b - a ≤ c, just the new word is appended to other words on the screen. If b - a > c, then everything on the screen disappears and after that the word you have typed appears on the screen.

For example, if c = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.

You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.

## Input Format
The first line contains two integers n and c (1 ≤ n ≤ 100 000, 1 ≤ c ≤ 109) — the number of words ZS the Coder typed and the crazy computer delay respectively.

The next line contains n integers t1, t2, ..., tn (1 ≤ t1 < t2 < ... < tn ≤ 109), where ti denotes the second when ZS the Coder typed the i-th word.

## Output Format
Print a single positive integer, the number of words that remain on the screen after all n words was typed, in other words, at the second tn.

## Examples
```input
6 5
1 3 8 14 19 20
```
```output
3
```
-----
```input
6 1
1 3 5 7 9 10
```
```output
2
```

## Note
The first sample is already explained in the problem statement.

For the second sample, after typing the first word at the second 1, it disappears because the next word is typed at the second 3 and 3 - 1 > 1. Similarly, only 1 word will remain at the second 9. Then, a word is typed at the second 10, so there will be two words on the screen, as the old word won't disappear because 10 - 9 ≤ 1.

Now solve the problem and return the code.