Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

   • (x+1,y) if S_i is R;
   • (x-1,y) if S_i is L;
   • (x,y+1) if S_i is U;
   • (x,y-1) if S_i is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

• 1\leq N,M,H,K\leq 2\times 10^5
• S is a string of length N consisting of R, L, U, and D.
• |x_i|,|y_i| \leq 2\times 10^5
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers, except for S.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

• 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

• 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

• 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

• 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

• 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

• 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

• Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i \leq N
• All values in input are integers.

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
• Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
• Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9

Problem Statement

Takahashi and Aoki will play a game of taking stones using a sequence (A_1, \ldots, A_K).

There is a pile that initially contains N stones. The two players will alternately perform the following operation, with Takahashi going first.

• Choose an A_i that is at most the current number of stones in the pile. Remove A_i stones from the pile.

The game ends when the pile has no stones.

If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?

Constraints

• 1 \leq N \leq 10^4
• 1 \leq K \leq 100
• 1 = A_1 < A_2 < \ldots < A_K \leq N
• All values in the input are integers.

Sample Input 1

10 2
1 4

Sample Output 1

5

Below is one possible progression of the game.

• Takahashi removes 4 stones from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 1 stone from the pile.
• Aoki removes 1 stone from the pile.

In this case, Takahashi removes 5 stones. There is no way for him to remove 6 or more stones, so this is the maximum.

Below is another possible progression of the game where Takahashi removes 5 stones.

• Takahashi removes 1 stone from the pile.
• Aoki removes 4 stones from the pile.
• Takahashi removes 4 stones from the pile.
• Aoki removes 1 stone from the pile.

Sample Input 2

11 4
1 2 3 6

Sample Output 2

8

Below is one possible progression of the game.

• Takahashi removes 6 stones.
• Aoki removes 3 stones.
• Takahashi removes 2 stones.

In this case, Takahashi removes 8 stones. There is no way for him to remove 9 or more stones, so this is the maximum.

Sample Input 3

10000 10
1 2 4 8 16 32 64 128 256 512

Sample Output 3

5136

Problem Statement

This is an interactive problem (a type of problem where your program interacts with the judge program through Standard Input and Output).

There are N bottles of juice, numbered 1 to N. It has been discovered that exactly one of these bottles has gone bad. Even a small sip of the spoiled juice will cause stomach upset the next day.

Takahashi must identify the spoiled juice by the next day. To do this, he decides to call the minimum necessary number of friends and serve them some of the N bottles of juice. He can give any number of bottles to each friend, and each bottle of juice can be given to any number of friends.

Print the number of friends to call and how to distribute the juice, then receive information on whether each friend has an upset stomach the next day, and print the spoiled bottle's number.

Constraints

• N is an integer.
• 2 \leq N \leq 100

Input/Output

This is an interactive problem (a type of problem where your program interacts with the judge program through Standard Input and Output).

Before the interaction, the judge secretly selects an integer X between 1 and N as the spoiled bottle's number. The value of X is not given to you. Also, the value of X may change during the interaction as long as it is consistent with the constraints and previous outputs.

First, the judge will give you N as input.

N

You should print the number of friends to call, M, followed by a newline.

M

Next, you should perform the following procedure to print M outputs. For i = 1, 2, \ldots, M, the i-th output should contain the number K_i of bottles of juice you will serve to the i-th friend, and the K_i bottles' numbers in ascending order, A_{i, 1}, A_{i, 2}, \ldots, A_{i, K_i}, separated by spaces, followed by a newline.

K_i A_{i, 1} A_{i, 2} \ldots A_{i, K_i}

Then, the judge will inform you whether each friend has a stomach upset the next day by giving you a string S of length M consisting of 0 and 1.

S

For i = 1, 2, \ldots, M, the i-th friend has a stomach upset if and only if the i-th character of S is 1.

You should respond by printing the number of the spoiled juice bottle X', followed by a newline.

X'

Then, terminate the program immediately.

If the M you printed is the minimum necessary number of friends to identify the spoiled juice out of the N bottles, and the X' you printed matches the spoiled bottle's number X, then your program is considered correct.

Notes

• Each output should end with a newline and flushing Standard Output. Otherwise, you may receive a TLE verdict.
• The verdict is indeterminate if your program prints an invalid output during the interaction or terminates prematurely. In particular, note that if a runtime error occurs during the execution of the program, the verdict may be WA or TLE instead of RE.
• Terminate the program immediately after printing X'. Otherwise, the verdict is indeterminate.
• The judge for this problem is adaptive, meaning that the value of X may change as long as it is consistent with the constraints and previous outputs.

Sample Input/Output

Below is an interaction with N = 3.

Problem Statement

You are in a store to buy N items. The regular price of the i-th item is P_i yen (the currency in Japan).

You have M coupons. You can use the i-th coupon to buy an item whose regular price is at least L_i yen at a D_i-yen discount.

Here, each coupon can be used only once. Besides, multiple coupons cannot be used for the same item.

If no coupon is used for an item, you will buy it for a regular price. Find the minimum possible total amount of money required to buy all the N items.

Constraints

• 1\leq N,M\leq 2\times 10^5
• 1\leq P_i\leq 10^9
• 1\leq D_i \leq L_i \leq 10^9
• All input values are integers.

Sample Input 1

3 3
4 3 1
4 4 2
2 3 1

Sample Output 1

4

Consider using the 2-nd coupon for the 1-st item, and the 3-rd coupon for the 2-nd item.

Then, you buy the 1-st item for 4-3=1 yen, 2-nd item for 3-1=2 yen, and 3-rd item for 1 yen. Thus, you can buy all the items for 1+2+1=4 yen.

Sample Input 2

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

Sample Output 2

37