Problem Statement

The magnitude of an earthquake is a logarithmic scale of the energy released by the earthquake. It is known that each time the magnitude increases by 1, the amount of energy gets multiplied by approximately 32.
Here, we assume that the amount of energy gets multiplied by exactly 32 each time the magnitude increases by 1. In this case, how many times is the amount of energy of a magnitude A earthquake as much as that of a magnitude B earthquake?

Constraints

• 3\leq B\leq A\leq 9
• A and B are integers.

Sample Input 1

6 4

Sample Output 1

1024

6 is 2 greater than 4, so a magnitude 6 earthquake has 32\times 32=1024 times as much energy as a magnitude 4 earthquake has.

Sample Input 2

5 5

Sample Output 2

1

Earthquakes with the same magnitude have the same amount of energy.

Problem Statement

There is an ultramarathon course totaling 100\;\mathrm{km}. Water stations are set up every 5\;\mathrm{km} along the course, including the start and goal, for a total of 21.

Takahashi is at the N\;\mathrm{km} point of this course. Find the position of the nearest water station to him.

Under the constraints of this problem, it can be proven that the nearest water station is uniquely determined.

Constraints

• 0\leq N\leq100
• N is an integer.

Sample Input 1

53

Sample Output 1

55

Takahashi is at the 53\;\mathrm{km} point of the course. The water station at the 55\;\mathrm{km} point is 2\;\mathrm{km} away, and there is no closer water station. Therefore, you should print 55.

Sample Input 2

21

Sample Output 2

20

Takahashi could also go back the way.

Sample Input 3

100

Sample Output 3

100

There are also water stations at the start and goal. Additionally, Takahashi may already be at a water station.

Problem Statement

AtCoder Inc. sells glasses and mugs.

Takahashi has a glass with a capacity of G milliliters and a mug with a capacity of M milliliters.
Here, G<M.

Initially, both the glass and the mug are empty.
After performing the following operation K times, determine how many milliliters of water are in the glass and the mug, respectively.

• When the glass is filled with water, that is, the glass contains exactly G milliliters of water, discard all the water from the glass.
• Otherwise, if the mug is empty, fill the mug with water.
• Otherwise, transfer water from the mug to the glass until the mug is empty or the glass is filled with water.

Constraints

• 1\leq K\leq 100
• 1\leq G<M\leq 1000
• G, M, and K are integers.

Sample Input 1

5 300 500

Sample Output 1

200 500

The operation will be performed as follows. Initially, both the glass and the mug are empty.

• Fill the mug with water. The glass has 0 milliliters, and the mug has 500 milliliters of water.
• Transfer water from the mug to the glass until the glass is filled. The glass has 300 milliliters, and the mug has 200 milliliters of water.
• Discard all the water from the glass. The glass has 0 milliliters, and the mug has 200 milliliters of water.
• Transfer water from the mug to the glass until the mug is empty. The glass has 200 milliliters, and the mug has 0 milliliters of water.
• Fill the mug with water. The glass has 200 milliliters, and the mug has 500 milliliters of water.

Thus, after five operations, the glass has 200 milliliters, and the mug has 500 milliliters of water. Hence, print 200 and 500 in this order, separated by a space.

Sample Input 2

5 100 200

Sample Output 2

0 0

Problem Statement

KEYENCE has a culture of reporting things as they are, whether good or bad.
So we want to check whether the reported content is exactly the same as the original text.

You are given two strings S and T, consisting of lowercase English letters.
If S and T are equal, print 0; otherwise, print the position of the first character where they differ.
Here, if the i-th character exists in only one of S and T, consider that the i-th characters are different.

More precisely, if S and T are not equal, print the smallest integer i satisfying one of the following conditions:

• 1\leq i\leq |S|, 1\leq i\leq |T|, and S_i\neq T_i.
• |S| < i \leq |T|.
• |T| < i \leq |S|.

Here, |S| and |T| denote the lengths of S and T, respectively, and S_i and T_i denote the i-th characters of S and T, respectively.

Constraints

• S and T are strings of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

abcde
abedc

Sample Output 1

3

We have S= abcde and T= abedc.
S and T have the same first and second characters, but differ at the third character, so print 3.

Sample Input 2

abcde
abcdefg

Sample Output 2

6

We have S= abcde and T= abcdefg.
S and T are equal up to the fifth character, but only T has a sixth character, so print 6.

Sample Input 3

keyence
keyence

Sample Output 3

0

S and T are equal, so print 0.

Problem Statement

There is a grid with H rows and W columns.

Each cell of the grid is land or sea, which is represented by H strings S_1, S_2, \ldots, S_H of length W. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left, and (i, j) is land if the j-th character of S_i is ., and (i, j) is sea if the character is #.

The constraints guarantee that all cells on the perimeter of the grid (that is, the cells (i, j) that satisfy at least one of i = 1, i = H, j = 1, j = W) are sea.

Takahashi's spaceship has crash-landed on a cell in the grid. Afterward, he moved N times on the grid following the instructions represented by a string T of length N consisting of L, R, U, and D. For i = 1, 2, \ldots, N, the i-th character of T describes the i-th move as follows:

• L indicates a move of one cell to the left. That is, if he is at (i, j) before the move, he will be at (i, j-1) after the move.
• R indicates a move of one cell to the right. That is, if he is at (i, j) before the move, he will be at (i, j+1) after the move.
• U indicates a move of one cell up. That is, if he is at (i, j) before the move, he will be at (i-1, j) after the move.
• D indicates a move of one cell down. That is, if he is at (i, j) before the move, he will be at (i+1, j) after the move.

It is known that all cells along his path (including the cell where he crash-landed and the cell he is currently on) are not sea. Print the number of cells that could be his current position.

Constraints

• H, W, and N are integers.
• 3 \leq H, W \leq 500
• 1 \leq N \leq 500
• T is a string of length N consisting of L, R, U, and D.
• S_i is a string of length W consisting of . and #.
• There is at least one cell that could be Takahashi's current position.
• All cells on the perimeter of the grid are sea.

Sample Input 1

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

Sample Output 1

2

The following two cases are possible, so there are two cells that could be Takahashi's current position: (3, 4) and (4, 5).

• He crash-landed on cell (3, 5) and moved (3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4).
• He crash-landed on cell (4, 6) and moved (4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5).

Sample Input 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

Sample Output 2

6

Problem Statement

There are N stations on a certain line operated by AtCoder Railway. The i-th station (1 \leq i \leq N) from the starting station is named S_i.

Local trains stop at all stations, while express trains may not. Specifically, express trains stop at only M \, (M \leq N) stations, and the j-th stop (1 \leq j \leq M) is the station named T_j.
Here, it is guaranteed that T_1 = S_1 and T_M = S_N, that is, express trains stop at both starting and terminal stations.

For each of the N stations, determine whether express trains stop at that station.

Constrains

• 2 \leq M \leq N \leq 10^5
• N and M are integers.
• S_i (1 \leq i \leq N) is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
• S_i \neq S_j \, (i \neq j)
• T_1 = S_1 and T_M = S_N.
• (T_1, \dots, T_M) is obtained by removing zero or more strings from (S_1, \dots, S_N) and lining up the remaining strings without changing the order.

Sample Input 1

5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

Sample Output 1

Yes
No
Yes
No
Yes

Sample Input 2

7 7
a t c o d e r
a t c o d e r

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes
Yes

Express trains may stop at all stations.

Problem Statement

There is a pond with a circumference of M, and on its shore stand one hut and N people.
For a real number x (0\leq x <M), define point x as the location that is x distance clockwise from the hut.
The i-th person is at point A_i. Multiple people may be standing at the same location.

Additionally, an integer C not greater than N is given. For i=0,1,\ldots,M-1, define X_i as follows:

1. Takahashi starts at point (i+0.5) and begins moving clockwise.
2. Takahashi continues moving (clockwise) as long as the total number of people he has met is less than C, and stops when it becomes C or more. Here, "meeting a person at point y" means that Takahashi reaches point y.
3. Let X_i be the number of people Takahashi met before stopping. Here, if there are multiple people at the point where Takahashi stopped, all the people there are counted as people he met, and particularly, X_i may be greater than C.

Find the sum of X_i over i=0,1,\ldots,M-1, that is, \displaystyle\sum_{i=0}^{M-1} X_i.

Constraints

• 1\leq N\leq 5\times 10^5
• 1\leq M\leq 10^{12}
• 0\leq A_i\leq M-1
• 1\leq C\leq N
• All input values are integers.

Sample Input 1

5 3 2
1 2 1 0 1

Sample Output 1

9

When i=0, Takahashi starts at point 0.5 and moves clockwise. Then, the following happens:

• At point 1, he meets the 1st, 3rd, and 5th people, a total of three people, and the total number of people met so far is 3. This is not less than C=2, so Takahashi stops there. Therefore, X_0=3.

When i=1, Takahashi starts at point 1.5 and moves clockwise. Then, the following happens:

• At point 2, he meets the 2nd person. The total number of people met so far is 1, so he continues moving.
• At point 0, he meets the 4th person, and the total number of people met so far is 2. This is not less than C=2, so Takahashi stops there. Therefore, X_1=2.

When i=2, Takahashi starts at point 2.5 and moves clockwise. Then, the following happens:

• At point 0, he meets the 4th person. The total number of people met so far is 1, so he continues moving.
• At point 1, he meets the 1st, 3rd, and 5th people, a total of three people, and the total number of people met so far is 4. This is not less than C=2, so Takahashi stops there. Therefore, X_2=4.

Therefore, the answer is X_0+X_1+X_2=3+2+4=9.

Sample Input 2

1 1000000000000 1
1

Sample Output 2

1000000000000

Regardless of the starting position, Takahashi stops when he meets the only person standing around the pond, who is at point 1.
Therefore, X_i=1 regardless of i, and the answer is 10^{12}.

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Some coins are placed on each cell, and there are A_{i,j} coins on cell (i,j).

Takahashi is initially at cell (1,1) and has x coins. Over the next H+W-1 days, several events will occur. On the k-th day (1\leq k\leq H+W-1), the following things happen in order:

1. Takahashi collects all the coins placed on the cell where he is currently located.
2. Hungry Takahashi consumes P_k coins from his hand to buy food. However, if he has fewer than P_k coins, he cannot buy food and collapses from hunger.
3. If k < H+W-1, Takahashi moves either one cell right or one cell down. He cannot leave the grid. If k=H+W-1, he does nothing.

When there exists a way for Takahashi to finish the next H+W-1 days without ever collapsing from hunger, find the minimum non-negative integer x that can be the number of coins Takahashi initially has.

Constraints

• H,W\geq 1
• H\times W \leq 2\times 10^5
• 1\leq A_{i,j}\leq 10^9
• 1\leq P_k\leq 10^9
• All input values are integers.

Sample Input 1

2 2
3 2
4 1
1 3 6

Sample Output 1

2

When x=2, Takahashi can act as follows to avoid collapsing from hunger:

• Initially, he is at cell (1,1) and has 2 coins.
• Day 1:
  1. He collects 3 coins placed on cell (1,1), so he has 5 coins.
  2. He consumes 1 coin to buy food, so he has 4 coins.
  3. He moves to cell (2,1) which is 1 below.
• Day 2:
  1. He collects 4 coins placed on cell (2,1), so he has 8 coins.
  2. He consumes 3 coins to buy food, so he has 5 coins.
  3. He moves to cell (2,2) which is 1 to the right.
• Day 3:
  1. He collects 1 coin placed on cell (2,2), so he has 6 coins.
  2. He consumes 6 coins to buy food, so he has 0 coins.

When x is 1 or less, Takahashi will collapse from hunger at some point no matter how he acts. Therefore, the answer is 2.

Sample Input 2

1 1
5
3

Sample Output 2

0

Even if Takahashi initially has no coins, he will not collapse from hunger.

Sample Input 3

4 7
35 29 36 88 58 15 25
99 7 49 61 67 4 57
96 92 3 49 49 36 90
72 89 40 44 24 53 45
55 43 23 71 77 6 94 19 27 21

Sample Output 3

20

Problem Statement

There is a skating rink represented by a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The skating rink has N obstacles. The i-th obstacle is placed at (X_i,Y_i).

In a single move, Takahashi chooses one of the four directions, up, down, left, or right, and keeps moving until he hits an obstacle.
When he hits an obstacle, he stops at the square right before the obstacle. Since the skating rink is surrounded by cliffs, it is prohibited to start a move in which he will never hit an obstacle.

Takahashi is initially at (s_x,s_y). He wants to make some number of moves to stop at (g_x,g_y).

Find the minimum number of moves required to end up at (g_x, g_y). If it is not possible, report the fact.

Constraints

• 1\leq H \leq 10^9
• 1\leq W \leq 10^9
• 1\leq N \leq 10^5
• 1\leq s_x,g_x\leq H
• 1\leq s_y,g_y\leq W
• 1\leq X_i \leq H
• 1\leq Y_i \leq W
• (s_x,s_y)\neq (g_x,g_y)
• (s_x,s_y)\neq (X_i,Y_i)
• (g_x,g_y)\neq (X_i,Y_i)
• If i\neq j, then (X_i,Y_i)\neq (X_j,Y_j).
• All values in input are integers.

Sample Input 1

7 8 7
3 4
5 6
1 4
2 1
2 8
4 5
5 7
6 2
6 6

Sample Output 1

4

In the figure, (s_x,s_y) is denoted by S and (g_x,g_y) is denoted by G.
By moving as (3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6), he can end up at (g_x,g_y) with 4 moves.

Sample Input 2

4 6 2
3 2
3 5
4 5
2 5

Sample Output 2

-1

He must stop at (g_x,g_y).
Note that just passing through (g_x,g_y) is not considered to be ending up at the goal.

Sample Input 3

1 10 1
1 5
1 1
1 7

Sample Output 3

-1

If he chooses to move to the left, Takahashi will fall down the cliff after passing through (g_x,g_y).
Note that it is prohibited to start a move in which he will never hit an obstacle, as the skating rink is surrounded by cliffs.