Problem A. Anastasia is jumping ≡

Statement

Anastasia is standing in the beginning of a string (at the first letter), consisting of N lowercase Latin letters. She can make unlimited number of jumps to the next letter in the string. She also can make at most one hyperjump to any letter that is standing in alphabet later than the current letter. For example, if Anastasia is standing at letter 'x', she can jump to any of letters 'y' and 'z' in the string.

Anastasia is a very curious girl. She is interested what is the minimal number of jumps (a hyperjump is also counted as an one jump) she needs to reach the last letter (the letter number N).

Input format

The first line contains an integer N — number of letters in the string.

Second line contains string consisting of N lowercase Latin letters.

Output format

Print one integer — the minimal amount of jumps Anastasia needs to reach the last letter.

Constraints

2 ≤ N ≤ 10⁵

Sample tests

6
badcab

2

10
edcbaedbca

5

26
zyxwvutsrqponmlkjihgfedcba

25

Problem B. Boasting doesn't add courage ≡

Statement

Nick is a skilled swimmer. He likes to swim in the high sea with a mask. But today he faced a problem — his way was blocked by a colony of Portuguese man o' war (a species of jellyfishes).

Nick noticed that they are arranged in N rows, length of each row is M meters. There is a gleam of 1 meter between each row, in which Nick can move freely to the right or to the left. In addition, there is free cells in some rows. Nick can use them to float between rows.

Nick has an underwater camera with him. That's why he decided to float through the colony and record a video to brag to friends after that.

However, boasting doesn't add courage. Therefore Nick wants to find out the length L (in meters) of the shortest way from the 1^st to the N^th row. L contains both: movements in a row and movements between rows. Nick can start swimming in any point of the first row and finish in any point of the last row.

The distance from the current row to the next is 1 meter. Note that Nick can only swim left/right in space between rows and forward (if there is no Portuguese man o' war in front of him). For a better understanding, look at the picture that illustrates the 2_nd example. The points in the picture mark the places where Nick stops in each row between his movements (Nick can't finish his swimming in the space between the rows, so the answer is always an integer number of meters).

Input format

The first line contains two integers N and M — measurements of the jellyfish colony.

It follows by N lines, M characters each — the colony description.

By '*' marked the place with jellyfish, by '.' — free place.

It is guaranteed that each row contains no less than 1 and no more than M − 1 Portuguese man o' war.

Output format

Print integer L — the length of the Nick's shortest way through the colony.

Constraints

2 ≤ N, M ≤ 2000

Sample tests

2 2
*.
.*

2

5 7
.*****.
**.**.*
.*****.
.****.*
.**.***

8

3 5
.****
*.**.
***.*

5

Problem C. Conscientiously counted waffels ≡

Statement

Group of n scientists returned to their camp quite late. They were so tired so they didn't eat any of their m waffles.

However during the night every scientist woke up once, all at different time. Everyone thought that he woke up first, because all the rest were asleep, so if at the moment there were x waffles, he thought that he is allowed to eat xn waffles. In case xn was not an integer, a scientist could round it up or down, depending on how hungry he was. So every scientist ate ⌊ xn⌋ or ⌈ xn⌉ waffles, where x is the number of remaining waffles at the moment he woke up.

At the morning remained k waffles, after every scientist woke up during the night. Nobody remembers, neither when he woke, nor how many waffles were there at this moment, nor how hungry he was. They were interested, what could be minimal m_min and maximal m_max number of waffles in the beginning?

Notice that it's possible, that some scientists ate zero waffles.

Input format

The first line contains two integers n and k.

Output format

Print two space separated integers — m_min and m_max.

Constraints

2 ≤ n ≤ 10⁵

1 ≤ k ≤ 10⁹

Sample tests

7 9

19 32

21 39

90 127

937 1045684

2843161 2844778

Problem D. Deft ninja ≡

Statement

Ninja wants to gain an artifact located in the field of size N ⋅ M.

There are guards in the field. Each of them is looking in one direction and turns clockwise in the end of each second, so after four seconds a guard makes full rotation. A guard raises the alarm if he sees the ninja located on the line of guards sight, and nobody is located between them. The artifact is too small and doesn't obstruct guards sight.

Initially the ninja is located in the cell marked 'N', the artifact is in the cell marked 'A', guards are located in the cells marked '>', '<', '^', 'v' accordingly to their initial sight direction. In the end of each second ninja can move one cell in any of four direction or stay in the same place.

It is guaranteed that in the cell with guard there are no ninja, artifact or another guard. Initially (during the zero second) none of guards can see the ninja.

Your task is to find the minimal number of seconds the ninja needs to reach the artifact without being noticed or tell, that it's impossible.

Input format

The first line contains two integers N and M — field size. Then follow N strings of M symbols describing the field.

Output format

Print one integer — the minimal number of seconds the ninja needs to reach the artifact without being noticed, or "-1" if it's impossible.

Constraints

2 ≤ N, M ≤ 1000

Sample tests

2 2
A>
.N

3

3 3
A.<
<.v
^Nv

-1

4 4
.^..
<A.v
..N.
.<..

4

5 5
A...<
.....
....v
...N.
>^<v.

9

Problem E. Endless expression ≡

Statement

«To infinity and beyond»

You are now in the Kingdom of Infinity.

In order to escape you need to find the value of the endless expression √[3]n + √[3]n + √[3]n + ... with specified accuracy (of course, that you are in the Kingdom of Infinity, decimal representation of the expression can be infinitely long).

Your answer will be accepted if it has absolute error at most 10⁻⁵. More specifically, if your answer is a and the jury answer is b, your answer will be accepted if |a − b| ≤ 10⁻⁵.

Input format

The first line contains an integer n.

Output format

Print the value of this infinite expression with specified accuracy.

Constraints

−10¹⁸ ≤ n ≤ 10¹⁸

Sample tests

1

1.32471796

67738

40.77223943

-2184

-13.00000000

Problem F. Fateful snap ≡

Statement

At the moment T (where T is an integer), Thanos was located in the point X, Y, Z (where X, Y, Z are also integers) and snapped his fingers. A radiation wave with intensity maxIntensity appeared immediately at this point. In rest points of space at this moment radiation was equal to 0.

Radiation wave is an expanding sphere. Radius of sphere increases one unit in one second, for example, it is equal to a after a seconds. At the time a any point of sphere surface (that is any point which distance to X, Y, Z is equal to a) has intensity equal to maxIntensity. Intensity is gradually decreasing in points inside the sphere.

To be more specific, let's consider a point located at the distance dist (dist ≤ a) from the point X, Y, Z. Intensity of radiation in this point is equal to maxIntensity − (a − dist). Intensity of radiation in points outside the sphere is equal to 0.

See the picture below for clarification. In this picture sphere surface with the maximal intensity (maxIntensity) is marked red. The space inside the sphere with gradually decreasing intensity is colored lighter. Notice, that there are limitations to parameter t we consider in this task, and it's guaranteed that maxIntensity is large enough that any point that gets in the sphere in moment t or earlier will never decrease to the intensity 0 or lower.

Tony stark decided to determine the place and the time of the snap of Thanos. He wants to use his chronotunnel he can send sensors with. A sensor can be sent in some specific time t in any point x, y, z. It measures radiation intensity in this point at the moment t, sends result to Tony Stark as a decimal number and burns. Stark has Q sensors in total, and he wants you to help him determine the place and the time of the snap using not more than Q sensor measurements. (Stark has not figured out yet, that he can go back in time and steal sensors from himself).

Output format

To provide the answer print the symbol "!" and then space separated integers T, X, Y, Z. Notice, that "!" and T also should be space separated. You should terminate immediately after printing the answer.

Interaction

It is guaranteed that Q measurements are enough to solve the problem. If your solution uses more than Q sensors, it will get "Wrong answer" for this test.

To send a sensor parameters description your program has to print line "? t x y z" (without quotes), where 0 ≤ t ≤ 3 ⋅ 10⁸ and t, x, y, z are integers. Jury program gives you one decimal value — result of the measurement at time t in the point x, y, z.

At the end of each sensor parameters description and after printing answer you have to print newline character \n and flush output buffer. To flush the buffer you can use (just after printing):

Constraints

0 ≤ T, X, Y, Z ≤ 10⁸

0 ≤ t ≤ 3 ⋅ 10⁸

0 ≤ x, y, z ≤ 10⁸

3 ⋅ 10⁸ < maxIntensity ≤ 10⁹

Q = 250

Sample tests

1000000000.000000000000000

0.000000000000000

1000000000.000000000000000

999999999.414213562384248

1000000000.000000000000000

0.000000000000000

999999995.000000000000000

700000010.000000000000000

? 11 100 100 101

? 10 100 100 101

? 10 100 100 100

? 12 100 101 101

? 15 100 103 104

? 15 101 103 104

? 20 100 103 104

? 300000000 100 100 100

! 10 100 100 100

Problem G. Guess the array ≡

Statement

Aleksey lost his favourite array a! He remembers that the array consisted of n non-negative integers, and its sum was equal to sum.

Recently Aleksey found his calculations on this array. His calculations consist of n numbers b_i such that

b_i = (a_i + a_i + 1)mod k for 1 ≤ i < n

b_n = (a_n + a₁)mod k (a_i — favourite array numbers)

Help Aleksey to find any correct favourite array a corresponding to the array b, or tell him that he has made a mistake, and there is no such array. Notice, that all elements of source array are non-negative integers that are not greater than 10⁴.

Input format

The first line contains three integers n, k, sum.

The next line contains n non-negative integers b_i.

Output format

If the answer exists, print "YES" in the first line and n space separated numbers of array a in the second line. If there are multiple answers, print any of them.

Print "NO" if there is no such array.

Constraints

2 ≤ n, k ≤ 10⁴

0 ≤ sum ≤ 10⁹

0 ≤ a_i ≤ 10⁴

0 ≤ b_i < k

Sample tests

6 4 21
3 1 3 1 3 3

YES
1 2 3 4 5 6

2 7 32
4 4

YES
11 21

6 4 21
1 3 2 1 3 2

NO