Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

• 1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
• 2 p: Find the coordinates of part p.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 2\times 10^5
• For the first type of query, C is one of R, L, U, and D.
• For the second type of query, 1\leq p \leq N.
• All numerical input values are integers.

Sample Input 1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

Sample Output 1

3 0
2 0
1 1
1 0
1 0

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

Problem Statement

The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)

For each i=1,2,\dots,N, solve the following problem.

• How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.

Constraints

• 1 \le M \le N \le 2 \times 10^5
• 1 \le A_1 < A_2 < \dots < A_M = N
• All input values are integers.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.

• From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
• From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
• From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2

0
1
0
0
2
1
0
0

Problem Statement

There is an N \times N grid, where each cell is either empty or contains an obstacle. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are also two players on distinct empty cells of the grid. The information about each cell is given as N strings S_1, S_2, \ldots, S_N of length N, in the following format:

• If the j-th character of S_i is P, then (i, j) is an empty cell with a player on it.

• If the j-th character of S_i is ., then (i, j) is an empty cell without a player.

• If the j-th character of S_i is #, then (i, j) contains an obstacle.

Find the minimum number of moves required to bring the two players to the same cell by repeating the following operation. If it is impossible to bring the two players to the same cell by repeating the operation, print -1.

• Choose one of the four directions: up, down, left, or right. Then, each player attempts to move to the adjacent cell in that direction. Each player moves if the destination cell exists and is empty, and does not move otherwise.

Constraints

• N is an integer between 2 and 60, inclusive.
• S_i is a string of length N consisting of P, ., and #.
• There are exactly two pairs (i, j) where the j-th character of S_i is P.

Sample Input 1

5
....#
#..#.
.P...
..P..
....#

Sample Output 1

3

Let us call the player starting at (3, 2) Player 1 and the player starting at (4, 3) Player 2.

For example, doing the following brings the two players to the same cell in three moves:

• Choose left. Player 1 moves to (3, 1), and Player 2 moves to (4, 2).

• Choose up. Player 1 does not move, and Player 2 moves to (3, 2).

• Choose left. Player 1 does not move, and Player 2 moves to (3, 1).

Sample Input 2

2
P#
#P

Sample Output 2

-1

Sample Input 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

Sample Output 3

10

Problem Statement

Takahashi has prepared N dishes for Snuke. The dishes are numbered from 1 to N, and dish i has a sweetness of A_i and a saltiness of B_i.

Takahashi can arrange these dishes in any order he likes. Snuke will eat the dishes in the order they are arranged, but if at any point the total sweetness of the dishes he has eaten so far exceeds X or the total saltiness exceeds Y, he will not eat any further dishes.

Takahashi wants Snuke to eat as many dishes as possible. Find the maximum number of dishes Snuke will eat if Takahashi arranges the dishes optimally.

Constraints

• 1 \leq N \leq 80
• 1 \leq A_i, B_i \leq 10000
• 1 \leq X, Y \leq 10000
• All input values are integers.

Sample Input 1

4 8 4
1 5
3 2
4 1
5 3

Sample Output 1

3

Consider the scenario where Takahashi arranges the dishes in the order 2, 3, 1, 4.

• First, Snuke eats dish 2. The total sweetness so far is 3, and the total saltiness is 2.
• Next, Snuke eats dish 3. The total sweetness so far is 7, and the total saltiness is 3.
• Next, Snuke eats dish 1. The total sweetness so far is 8, and the total saltiness is 8.
• The total saltiness has exceeded Y=4, so Snuke will not eat any further dishes.

Thus, in this arrangement, Snuke will eat three dishes.

No matter how Takahashi arranges the dishes, Snuke will not eat all four dishes, so the answer is 3.

Sample Input 2

2 1 1
3 2
3 2

Sample Output 2

1

Sample Input 3

2 100 100
3 2
3 2

Sample Output 3

2

Sample Input 4

6 364 463
230 381
154 200
328 407
339 94
193 10
115 309

Sample Output 4

3

Problem Statement

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

You and the judge will follow the procedure below. The procedure consists of phases 1 and 2; phase 1 is immediately followed by phase 2.

(Phase 1)

• The judge decides an integer N between 1 and 10^9 (inclusive), which is hidden.
• You print an integer M between 1 and 110 (inclusive).
• You also print an integer sequence A=(A_1,A_2,\ldots,A_M) of length M such that 1 \leq A_i \leq M for all i = 1, 2, \ldots, M.

(Phase 2)

• The judge gives you an integer sequence B=(B_1,B_2,\ldots,B_M) of length M. Here, B_i = f^N(i). f(i) is defined by f(i)=A_i for all integers i between 1 and M (inclusive), and f^N(i) is the integer resulting from replacing i with f(i) N times.
• Based on the given B, you identify the integer N that the judge has decided, and print N.

After the procedure above, terminate the program immediately to be judged correct.

Constraints

• N is an integer between 1 and 10^9 (inclusive).

Input and Output

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

(Phase 1)

• First, print an integer M between 1 and 110 (inclusive). It must be followed by a newline.

M

• Then, print a sequence A=(A_1,A_2,\ldots,A_M) of length M consisting of integers between 1 and M (inclusive), with spaces in between. It must be followed by a newline.

A_1 A_2 \ldots A_M

(Phase 2)

• First, an integer sequence B=(B_1,B_2,\ldots,B_M) of length M is given from the input.

B_1 B_2 \ldots B_M

• Find the integer N and print it. It must be followed by a newline.

N

If you print something illegal, the judge prints -1. In that case, your submission is already considered incorrect. Since the judge program terminates at this point, it is desirable that your program terminates too.

Notes

• After each output, add a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
• If an invalid output is printed during the interaction, or if the program terminates halfway, the verdict will be indeterminate.
• After you print the answer (or you receive -1), immediately terminate the program normally. Otherwise, the verdict will be indeterminate.
• Note that an excessive newline is also considered an invalid input.

Sample Interaction

The following is a sample interaction with N = 2.