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

# Problem
High school student Vasya got a string of length n as a birthday present. This string consists of letters 'a' and 'b' only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.

Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?

## Input Format
The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.

The second line contains the string, consisting of letters 'a' and 'b' only.

## Output Format
Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.

## Examples
```input
4 2
abba
```
```output
4
```
-----
```input
8 1
aabaabaa
```
```output
5
```

## Note
In the first sample, Vasya can obtain both strings "aaaa" and "bbbb".

In the second sample, the optimal answer is obtained with the string "aaaaabaa" or with the string "aabaaaaa".

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
100 years have passed since the last victory of the man versus computer in Go. Technologies made a huge step forward and robots conquered the Earth! It's time for the final fight between human and robot that will decide the faith of the planet.

The following game was chosen for the fights: initially there is a polynomial

P(x) = anxn + an - 1xn - 1 + ... + a1x + a0,

Polynomial P(x) is said to be divisible by polynomial Q(x) if there exists a representation P(x) = B(x)Q(x), where B(x) is also some polynomial.

Some moves have been made already and now you wonder, is it true that human can guarantee the victory if he plays optimally?

## Input Format
The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, |k| ≤ 10 000) — the size of the polynomial and the integer k.

The i-th of the following n + 1 lines contain character '?' if the coefficient near xi - 1 is yet undefined or the integer value ai, if the coefficient is already known ( - 10 000 ≤ ai ≤ 10 000). Each of integers ai (and even an) may be equal to 0.

Please note, that it's not guaranteed that you are given the position of the game where it's computer's turn to move.

## Output Format
Print "Yes" (without quotes) if the human has winning strategy, or "No" (without quotes) otherwise.

## Examples
```input
1 2
-1
?
```
```output
Yes
```
-----
```input
2 100
-10000
0
1
```
```output
Yes
```
-----
```input
4 5
?
1
?
1
?
```
```output
No
```

## Note
In the first sample, computer set a0 to  - 1 on the first move, so if human can set coefficient a1 to 0.5 and win.

In the second sample, all coefficients are already set and the resulting polynomial is divisible by x - 100, so the human has won.

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
On the coordinate plane there is a square with sides parallel to the coordinate axes. The length of the square side is equal to a. The lower left corner of the square coincides with the point (0, 0) (the point of the origin). The upper right corner of the square has positive coordinates.

You are given a point with coordinates (x, y). Your task is to determine whether this point is located strictly inside the square, on its side, or strictly outside the square.

## Input Format
The first line contains three integers a, x and y (1 ≤ a ≤ 1000,  - 1000 ≤ x, y ≤ 1000) — the length of the square side and the coordinates of the point which should be checked.

## Output Format
Print one integer:

- 0, if the point is located strictly inside the square;
- 1, if the point is located on the side of the square;
- 2, if the point is located strictly outside the square.

## Examples
```input
2 1 1
```
```output
0
```
-----
```input
4 4 4
```
```output
1
```
-----
```input
10 5 -4
```
```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: 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 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
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 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
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 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
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 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
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 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
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 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
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 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 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.