Problem Statement

E869120 went to a famous sushi restaurant: "AtCoder Kuru-kuru Sushi".
In this restaurant, N sushi is being sold. They are conveniently numbered 1 through N. He can pick sushi i at a_i+kT (k is non-negative integer) seconds after he came at "AtCoder Kuru-kuru Sushi". (Note that he can also pick a sushi right after he came)

He want to eat N sushi in ascending order: from sushi 1 to sushi N. In addition, since his eating speed is very fast, he can eat a sushi in 0 second. Moreover, he always eat sushi immediately when he pick a sushi because he is greedy.
How many seconds are needed to eat all sushi in order?

Input

Input is given from Standard Input in the following format:

N T
a_1 a_2 a_3 ... a_N

Output

Print the minimum number of seconds to eat all sushi in ascending order.

Sample Input 1

1 6
4

Sample Output 1

4

He can pick sushi 1 at 4, 10, 16, 22, \cdots seconds after he came at the restaurant.
If he pick sushi 1 at 4 seconds after he came, he can eat all sushi in ascending order in 4 seconds!

Sample Input 2

3 10
3 7 2

Sample Output 2

12

He can pick and eat sushi 1 at 3 seconds, sushi 2 at 7 seconds, sushi 3 at 12 seconds after he came at the restaurant.
Also, he can pick sushi 3 at 2 seconds after he came, but because he is greed, he eat the sushi immediately. So to eat sushi in ascending order, it took at least 12 seconds.

Sample Input 3

6 15
8 6 9 1 2 0

Sample Output 3

45

Problem Statement

E869120 the coder is going to create an emblem which is consist of N+M circles conveniently numbered 1, 2, 3, \cdots, N+M, to celebrate the holding of "square869120Contest #5".
He has already decided the center point (x_i, y_i) and radius r_i, for circle i \ (1 \leq i \leq N).
He has also decided the center point (x_i, y_i) for circle i (N+1 \leq i \leq N+M), but he hasn't decided the radius of these circles.
Circle can contact with other circles, but no circle can intersect to or enclose any other circles.
Please maximize the radius of the smallest circle in the emblem.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1 r_1
x_2 y_2 r_2
 :    :
x_N y_N r_N
x_{N+1} y_{N+1}
x_{N+2} y_{N+2}
 :    :
x_{N+M} y_{N+M}

Output

Print the maximum value of "the radius of the smallest circle".
The output will be judged correct when the absolute or relative error is at most 10^{-6}.

Sample Input 1

0 2
6 3
2 4

Sample Output 1

2.061552812808830

In this case, if you set the radius of circle 1, 2 to \frac{\sqrt{17}}{2}, the two circles contacts, and the radius of the smallest circle will be maximized.
An example of emblem is as follows:

Sample Input 2

0 5
8 6
9 1
2 0
1 0
0 1

Sample Output 2

0.500000000000000

An example of emblem is as follows:

Sample Input 3

3 0
5 2 3
-1 0 2
2 -6 4

Sample Output 3

2.000000000000000

In this case, there is no circle which the radius has not been decided. So, obviously, the radius of the smallest circle is always 2.

Sample Input 4

1 1
0 0 5
6 -3

Sample Output 4

1.708203932499369

In this case, you can maximize the radius of smallest circle if you set the radius of circle 2 to 3 \sqrt{5} - 5.
An example of emblem is as follows:

Problem Statement

E869120 and square1001 have correct bracket sequences with same length. "Correct bracket sequence" is defined as follows:

• () is a correct bracket sequence.
• If X is a correct bracket sequence, the concatenation of (, X, ) in this order is also a correct bracket sequence.
• If X and Y are correct bracket sequences, the concatenation of X and Y in this order is also a correct bracket sequence.
• Every correct bracket sequence can be derived from the rules above.

Let the bracket sequence of E869120 as A, and the bracket sequence of square1001 as B. chokudai performed the following operations from A and B.
Note that A and B should have equal length.

• For each character of B, if it is (, he changed to ). If it is ), he changed to (. After this operation, he defined an empty string C, and he performed either of the two operations while A or B is non-empty string.
• Insert the first character of A into the end of string C. After this, delete the first character of A.
• Insert the first character of B into the end of string C. After this, delete the first character of B.

You are given a string S. Please check if it is possible to be S=C or not.

Input

Input is given from Standard Input in the following format. Note: You should answer Q queries. The string S in i-th query is S_i.

Q
S_1
S_2
 :
S_Q

Output

Print Q lines.
In i-th line, print Yes if it is possible to be S_i = C, and print No if it is not possible to be S_i = C.

Sample Input 1

4
(())
)()(
(())
)(()

Sample Output 1

No
Yes
No
Yes

In the 2nd query, if A is "()", B = "()" and chokudai did operations in order of BAAB, C should be )()(. In this case, A, B, C changes as follows:

• A = "()", B = ")(", C = "" (After chokudai flips each character of B)
• A = "()", B = "(", C = ")"
• A = ")", B = "(", C = ")("
• A = "", B = "(", C = ")()"
• A = "", B = "", C = ")()("

Sample Input 2

1
(())(()(

Sample Output 2

No

In this case, there are 5 (s and 3 )s. Because the number of character ( and the number of character ) is the same for All correct bracket sequence, it is not possible to be S=C.

Sample Input 3

11
))(((()()())
))((())(())(
()())))(()((
)(()())()()(
)(())())(()(
)(()))()((()
)()()()())((
(())(()())()
)(())(()())(
((()())(()))
)))()())()()

Sample Output 3

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No

Problem Statement

Battle with E869120!
There is a grid with H rows and W columns. The square at the i-th row and j-th column will be denoted as (i, j). E869120 came up with following game which uses this grid.
At first, there are a token at (1, 1). Each player is supposed to place a token in turns, but they can place token in the square if and only if this square satisfies both following two condutions:

• There are no token in this square.
• Among the 4-adjacent (up, down, left, right) square, there are at least one square which contains token.

The player who placed a token in (H, W) wins.
E869120 offered you to play this game. You can choose whether you play first or E869120 play first. Your objective is to win this game.

Input and Output

This problem is "interactive task" (the task which has to take communications with input and output of program), so the format of input/output is special.

At first, the number of rows H and the columns W, are given in the input in following format:

H W

Then, your program must print whether you play first or E869120 plays first. If you play first, print First, otherwise, print Second. In the end you must put a line-break.

After that, the game starts. If you play first it will start from (☆), and if E869120 play first it will start from (★). It will repeat (☆) and (★) until the game ends.

(☆) It is your turn. Your program must decide where your program put a token. You must put line-break in the end.

x y

(★) It is E869120's turn. Your program will know the square (X, Y) which E869120 placed token from Standard Input in following format:

X Y

If (X, Y) = (-1, -1) it indicates the victory of your program, and it will be given after you put a token in (H, W). If (X, Y) = (H, W) it indicates that your program lost the game. In both case you have to terminate your program.

If your output format is invalid or the place that your program will put token is invalid, the verdict is undefined (it means it does not necessarily get WA). And also, you must flush Standard Output.**

Can you beat E869120?

Constraints

• H, W are integers between 1 and 50 (inclusive).
• (H, W) \neq (1, 1).

Problem Statement

E869120 the Coder is thinking about going to a skating rink which size is H \times W. The upper-left cell is (1,1), and the lower-right cell is (H,W).
The skating rink consists of 1 goal cell, some ice cells and some concrete cells.

The skating rink has characteristics as follows:

• Skaters move to the same direction while they're moving on ice cells.
• Skaters can change direction if and only they are stopping.
• If the skater came on the goal cell, he/she completes the game. However, if the skater came outside the skating rink, he/she will no longer able to complete the game.

Moreover, his skateboard is broken, so the moving speed will change as follows:

• It takes k seconds to move one cell. Initially, k is 1.
• If the skateboard come on a concrete cell, k will increase by 1.
• He can move only 4 directions: up, down, left, right.

He want to know the minimum time to complete the game for each starting cell.
Please write the program instead of E869120.

Input

Input is given from Standard Input in the following format:

H W
c_{1,1}c_{1,2}c_{1,3} ... c_{1,W}
c_{2,1}c_{2,2}c_{2,3} ... c_{2,W}
c_{3,1}c_{3,2}c_{3,3} ... c_{3,W}
...
c_{H,1}c_{H,2}c_{H,3} ... c_{H,W}

In 1-st line, the size of the skating link H, W is given.
From 2-nd line to H+1-th line, the state of skating link is given. The state of each cell is represents as follows:

• . means that the cell is an ice cell.
• # means that the cell is a concrete cell.
• G means that the cell is a goal cell.

Output

Print H lines in the following format:

d_{1,1} d_{1,2} d_{1,3} ... d_{1,W}
d_{2,1} d_{2,2} d_{2,3} ... d_{2,W}
d_{3,1} d_{3,2} d_{3,3} ... d_{3,W}
...
d_{H,1} d_{H,2} d_{H,3} ... d_{H,W}

d_{i,j} means the minimum time if he starts from cell (i,j). If he cannot reach the goal cell from (i,j), the value of d_{i,j} is -1.

Sample Input 1

6 6
......
.#....
......
......
......
...#.G

Sample Output 1

-1 -1 -1 9 -1 5
-1 -1 -1 8 -1 4
-1 -1 -1 7 -1 3
-1 -1 -1 6 -1 2
-1 -1 -1 5 -1 1
7 6 5 2 1 0

The above-mentioned picture represents the skating rink.
If he start from (2, 4), it takes 8 seconds.

Sample Input 2

1 8
#####G##

Sample Output 2

15 10 6 3 1 0 1 3

The above-mentioned picture represents the skating rink.
If he start from (1, 1), it takes 8 seconds.

Sample Input 3

9 9
....#..#.
#........
....#....
.#......#
...###...
##....#.#
....#...#
#....#...
.#.#..#.G

Sample Output 3

54 37 52 29 38 38 17 53 18
43 36 60 28 37 37 16 65 17
40 35 38 27 26 36 15 39 16
35 22 21 20 19 18 14 16 10
28 27 26 16 16 25 13 36 9
28 17 16 15 14 13 7 9 5
18 17 16 14 8 7 6 5 2
41 22 52 13 15 37 5 51 1
22 14 13 7 6 5 2 1 0

Problem Statement

There are N foods in AtCoder Café, which is conveniently numbered 1 through N. The deliciousness of food i is exactly a_i.
square1001 is going to have Q lunches. In i-th lunch, he will select the most delicious food (the food which has highest deliciousness) among the food which the number is between l_i and r_i (inclusive). If there are no such food, he won't eat lunch this time.

You are devil and you can erase M foods from the lunch menu and their menu will no longer able to select. Your objective is to minimize the total deliciousness of food square1001 selects.
Calculate the minimum value of total deliciousness of food square1001 selects.

Input

Input is given from Standard Input in the following format:

N M Q
a_1 \ a_2 \ a_3 \ \cdots \ a_N
l_1 \ r_1
l_2 \ r_2
l_3 \ r_3
 :  :
l_Q \ r_Q

Output

Print the minimum value of total deliciousness of food square1001 selects, in one line.

Sample Input 1

5 2 5
4 9 6 3 8
1 3
2 4
3 5
1 4
2 5

Sample Output 1

27

If you delete food 2 and 3, the maximum deliciousness is 4, 3, 8, 4, 8 in order.
The total deliciousness is 27.

Sample Input 2

5 0 4
8 6 9 1 2
1 3
4 5
2 5
4 4

Sample Output 2

21

Sample Input 3

8 5 3
1 1 1 1 1 1 1 1
2 5
1 3
6 8

Sample Output 3

1

Problem Statement

In the year 22XX, there were many poisonous snakes in AtCoder Kingdom. The king of AtCoder Kingdom, chokudai, locked all poisonous snakes he found in storage to exterminate this snake, but three years later poisonus snakes started to emerge again.
In Square Park in AtCoder Kingdom, there are H \times W colored squares (red, green, or blue) which forms a grid with H rows and W columns.
Some escaped snakes are going to try to mimic the colored squares in Square Park, to avoid getting caught by the king, chokudai.

Today, a poisonous snake escaped to Square Park. This snake is divided into |S| part from head to tail, and color of the i-th part is S_i. S consists of 'R', 'G', and 'B', and it denotes red, green, and blue, respectively.
If the snake is in Square Park, the adjacent parts should be in adjacent cells. The snake can mimic the colored squares completely if and only if every part of the snake has same color as the square that this part is in.

The snake wants to believe that itself will not be locked in the storage again, so the snake asked you to construct the coloring of Square Park and the placement of the snake.

Input

Input is given from the Standard Input in the following format:

S

Subtasks

Subtask 1 [80 points]

• |S| \leq 10 \ 000. (10 cases)

Subtask 2 [320 points]

• |S| \leq 15 \ 000. (10 + 10 = 20 cases)

Subtask 3 [800 points]

• |S| = 1 \ 000 \ 000. (20 cases)

Scoring

Scoring in Subtask 3 is special.

Let L be the maximum value of max(H,W) among all subtask-3 cases. Your score will be calculated as follows:

• If L \leq 30, you will get 800 points.
• If 31 \leq L \leq 40, you will get 1470 - 24L points.
• If 41 \leq L \leq 50, you will get 1270 - 19L points.
• If 51 \leq L \leq 100, you will get floor(620 \times 3^{1-\frac{L}{30}} + 20) points.

You can see this google drive file to look scores of subtask 3 when 30 \leq L \leq 100.

Sample Input 1

RGB

Sample Output 1

3 3
RGB
RGB
RGB
1 1
RR

The snake can mimic as follows:

Sample Input 2

GBRBGBR

Sample Output 2

4 3
GBR
RGR
RBR
RRR
1 1
RRLDDD

The snake can mimic as follows:

Sample Input 3

RGBGRGRBRR

Sample Output 3

3 4
RGBG
BRGR
RRRR
1 1
RRRDLLLRD

Problem Statement

E869120 the Coder decided to give a string to square1001 as a present each year for the next Q years.
Since E869120's favorite string is S, he also decided to "pick" the string, which he'll give as a present, from S.
Moreover, there's "AtCoder percepts" which has been told from ancient times, so he also decided to determine the string based on this percepts.

The contents of "AtCoder percepts" is as follows:

• When you will give a string as a present, you should decide the string as follows.
• Let T be the set of substring (not necessarily contiguous) of S.
• You should give K-th string of T in lexicographical order.

For example, if his favorite string is aqua, T will be [a,aa,aq,aqa,aqu,aqua,au,aua,q,qa,qu,qua,u,ua]. If K=10, you should give qa as a present, because qa is the 10-th string in T.

However, the value of K will change every year. The i-th year of K will be K_i.
Please answer the last p_i characters of string which you should give to square1001 in i-th year.

Input

Input is given from Standard Input in the following format:

S
Q
K_1 p_1
K_2 p_2
K_3 p_3
...
K_Q p_Q

Output

• Print Q lines.
• In i-th line, print the last p_i characters of substring of the string which he should give in i-th year.
• If there is no string which is applicable, print "-1".
• If the string which he should give is less than p_i characters, print the string. For example, if p_i=7 and string = "abcde", print "abcde".

Sample Input 1

aqua
16
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
10 10
11 10
12 10
13 10
14 10
15 10
16 10

Sample Output 1

a
aa
aq
aqa
aqu
aqua
au
aua
q
qa
qu
qua
u
ua
-1
-1

Please look the example in the problem statement.

Sample Input 2

tourist
2
76 10
76 4

Sample Output 2

tourist
rist

In 2-nd query, the answer is "tourist". But you should output the last 4 characters: "rist", because p_2 = 4.

Sample Input 3

eightsixnineonetwozero
6
869120 100
869120 10
869120 8
869120 6
869120 4
869120 2

Sample Output 3

eihinieonetwoze
ieonetwoze
onetwoze
etwoze
woze
ze

Problem Statement

One day, E869120 the Coder went to "AtCoder Natural Park".
The park represented as H*W grid. The top-left corner cell is (1,1) and the bottom-right corner cell is (H,W).
In addition, N gems drop in the park. In each cell, there are no more than 1 gem drops.

He want to collect all gems in the park.
He have "special smell-sense", so if there are 1 or more gems in relative-position that he decide beforehand, he think that "there is a gem near me".
The example of "relative position" is as follows:

In the left picture, if E869120 exists in the cell (4, 4), gems in cell (6, 5) and (2, 4) is "near". Suppose his relative position is (0, 0). In this case, the relative position of gem in example is (2, 1) and (-2, 0) in order. To see the picture, both (2, 1) and (-2, 0) is near.
But (2, 3) isn't near because its relative position is (-2, -1) and it is not near as long as see the picture.

However, he can move to one of 4-adjacent cells which share a side in 1 second. If there is a gem on the cell that E869120 exists, he pick it automatically in 0 second.
Initially, he is on the cell (1, 1). Please write the program that collect all gems in the park as fast as possible.

Input and Output

This problem is "interactive task" (the task which has to take communications with input and output of program), so the format of input/output is special.

First, you are given the size of "AtCoder Natural Park": H and W. You are also given the number of gems: N. The input format is as follows:

H W N

Second, you must set the relative-direction which includes "near", to make E869120's "special smell-sense".

P
x_1 y_1
x_2 y_2
...
x_P y_P

In the 1-st line, you should output the number of relative-position which include "near": P. 0 \leq P \leq 500 should be satisfied.
From the 2-nd line to P+1-th line, you should output relative-position: (x_i, y_i). x_i,y_i should be greater than -10^9 and less than 10^9. If there is gem on the cell that E869120 exists, he pick it instantly. So, (x_i, y_i) should not be (0, 0).

Next, it repeats the following two processes (☆) and (★) alternately (the first process is (☆)).

(☆) You are given an information as follows:

S

The information is classified as follows:

• far: There is no gems in his cells. In addition, there is no gem in relative-position that you set.
• close: There is no gems in his cells. In addition, there is 1 or more gems in relative-position that you set.
• get-far: There is a gem in his cells, so E869120 picks it. In addition, there is no gem in relative-position that you set after he picks.
• get-close: There is a gem in his cells, so E869120 picks it. In addition, there is 1 or more gems in relative-position that you set after he picks.
• get-clear: There is a gem in his cells, so E869120 picks it. In addition, all gems collected. You have to terminate your program if you program is given get-clear.

(★) E869120 moves. You should print as follows:

c

• If c is L, it means he moves to the left cell.
• If c is R, it means he moves to the right cell.
• If c is U, it means he moves to the up cell.
• If c is D, it means he moves to the down cell.
• He should not move to outside of the park.

Scoring

There are 15 testcases in this problem. For each cases, the max score is 100 points.
Let L be the number of moves. The point is calculated as follows:

• If L \leq 2 \ 100, 100 points.
• If 2 \ 101 \leq L \leq 2 \ 260, floor(100 - \frac{L - 2100}{8}) points.
• If 2 \ 261 \leq L \leq 2 \ 540, floor(80 - \frac{L - 2260}{14}) points.
• If 2 \ 541 \leq L \leq 3 \ 000, floor(60 - \frac{L - 2540}{25}) points.
• If 3 \ 001 \leq L \leq 5 \ 000, floor(41.6 - \frac{L - 3000}{125}) points.
• If 5 \ 001 \leq L \leq 6 \ 000, 24 points.
• If 6 \ 001 \leq L \leq 7 \ 000, 21 points.
• If 7 \ 001 \leq L \leq 8 \ 000, 18 points.
• If 8 \ 001 \leq L \leq 9 \ 000, 15 points.
• If 9 \ 001 \leq L \leq 10 \ 000, 3 points.

The graph that represents the correlation between the number of moves and score is as follows:

Sample Input and Output

The state of the park and the relative direction that includes "near" is as follows:

The interaction between computer and judge is as follows: