Problem Statement

Consider the following rhythm‑action game on the real line.

There are N buttons. The i‑th button (1 \le i \le N) appears at coordinate X_i exactly T_i seconds after the game starts. Each button disappears D + 0.5 seconds after it appears.

The player starts at coordinate 0 at time 0, and must press all N buttons to win the game. The buttons may be pressed in any order. However, after pressing a button and before pressing another, the player must visit coordinate 0 at least once. Violating this rule results in disqualification.

Ms. AtCoder can move at speed 1 on the line. Can she win the game? Pressing a button takes negligible time.

Solve \mathrm{TESTCASES} test cases.

Constraints

• 1 \le \mathrm{TESTCASES} \le 100\,000
• 1 \le N \le 5\,000
• 0 \le D \le 10^{12}
• 0 \le T_1 \le T_2 \le \dots \le T_N \le 10^{12}
• 1 \le X_i \le 10^{12}
• The sum of N over all test cases is at most 100\,000.
• The sum of N^2 over all test cases is at most 2.5 \times 10^7.
• All input values are integers.

Sample Input 1

4
2
10
30 20
50 10
2
9
30 20
50 10
4
185
0 40
0 30
0 20
0 10
5
1312372641
141421356 314159265
237309504 358979323
880168872 846264338
4209698078 327950288
5696718753 419716939

Sample Output 1

Yes
No
Yes
No

For the first test case, the game can be won as follows, so the first line contains Yes.

For the second test case, the game is unwinnable, so the second line contains No.
For the third test case, the game is winnable, so the third line contains Yes.
For the fourth test case, the game is unwinnable, so the fourth line contains No.

Problem Statement

An AGC word is a string of length at least 2 that contains the same number of A’s and C’s, and in every prefix, A’s make up at least half of the characters. You are given a string S of length 2N consisting of N A’s and N C’s. For each k = 1, 2, \dots, K, answer the following question.

A blackboard shows a string that is a concatenation of k copies of S. To turn it into an AGC word, perform the operations below in the order written:

1. Perform exactly once:
   • Choose integers (l, r) (1 \le l \le r \le 2kN) and reverse the l-th through r-th characters of the string.
2. Perform zero or more times:
   • Swap two adjacent characters of the string.

What is the minimum number of swaps required?

Constraints

• 1 \le N \le 1\,000\,000
• 1 \le K \le 300\,000
• S is a length‑2N string consisting of N A’s and N C’s.
• N and K are integers.

Sample Input 1

1 2
AC

Sample Output 1

0
0

For k = 1, the initial string is AC;
For k = 2, it is ACAC.

Both are already AGC words, so choosing, say, (l, r) = (1, 1) yields 0 swaps.

Sample Input 2

5 1
CACAAACCCA

Sample Output 2

1

For k = 1, the string is CACAAACCCA. By following the steps below, the sequence needs only one swap:

1. Choose (l, r) = (1, 4) and reverse the 1-st through 4-th characters. The string is now ACACAACCCA.
2. Swap the 9-th and 10-th characters. The string is now ACACAACCAC, which is an AGC word.

Sample Input 3

10 10
ACCCAAAACCCACCACAACA

Sample Output 3

1
2
3
3
3
3
3
3
3
3

Sample Input 4

50 10
ACCCCACAACAAAACCAACCCCACCAACACCAAAACACACAAAACCCCCACCAACACAACAACCCCAACAAACCCAACACACCCACACCAAACCCAAACA

Sample Output 4

10
17
20
22
23
24
25
26
26
26

Sample Input 5

72 10
CCCCACAAAAACCCACACCAAACCACCCCCAAAAACACCACCCCCAAAAAAACAAAAAACCCCCCACCCAAACAACACCACCACAAACCCAACCAACAACCCAAAACAACCCCACCACACACCACACCCACAAACACAACAACA

Sample Output 5

28
42
51
54
57
60
63
64
65
66

Problem Statement

AtCoder City is represented by an N \times N grid. Let (i, j) denote the cell at the i‑th row from the top (1 \le i \le N) and the j‑th column from the left (1 \le j \le N).

Aoki performed the following exercise K times for marathon training.

1. Start from cell (1, 1).
2. Repeat the following action 2N-2 times to reach cell (N, N):
   • Move one cell down or right. If both moves are possible, choose the one whose destination cell has been visited fewer times in the previous exercises. If the counts are equal, choose the downward move.

Print the path taken in the K‑th exercise.

Constraints

• 2 \le N \le 100
• 1 \le K \le 10^{18}
• All input values are integers.

Sample Input 1

5 4

Sample Output 1

RRDDRRDD

The 1st, 2nd, 3rd, and 4th exercises go as follows, so the answer is RRDDRRDD.

Sample Input 2

10 869120

Sample Output 2

RDRRRDRDRDRDRDDDRD

Problem Statement

This is an interactive problem.

There are \tbinom{2N}{N} cards numbered 1 to \tbinom{2N}{N} on a desk. Card i (1 \le i \le \tbinom{2N}{N}) shows on its front the i‑th string in lexicographic order among the strings consisting of N zeros and N ones.

Witch Alice writes one of the first N uppercase letters (for example, A or B if N = 2) on the back of each card, then performs the following magic T times.

A single magic

1. The host announces a letter s among the first N uppercase letters.
2. The host writes a length-2N string of all 0 on the blackboard.
3. For i = 1, 2, \dots, N in this order, do the following. Here, a_1, b_1, \dots, a_N, b_N are distinct integers from 1 to 2N.
   • First, the host tells Alice integers a_i and b_i.
   • Then, Alice chooses exactly one of the a_i-th and b_i-th characters of the string on the blackboard, and sets it to 1.
4. Let x be the final string on the blackboard. Exactly one card shows x on its front; look at its back. The magic succeeds if and only if the letter on its back equals s.

Note that Alice learns a_{i+1} and b_{i+1} only after choosing which of the a_i-th and b_i-th characters to set to 1.

Implement a strategy that makes all T magics succeed. Now, let us begin.

Constraints

• 2 \le N \le 10
• 1 \le T \le 5\,000
• The letter s is among the first N uppercase letters.
• 1 \le a_i < b_i \le 2N
• a_1, b_1, a_2, b_2, \dots, a_N, b_N are distinct.
• a_1, b_1, a_2, b_2, \dots, a_N, b_N, s are fixed before the interaction starts.
• N, T, a_i, b_i are integers.

Input and Output

First, read the integers N and T given from Standard Input in the following format:

N T

Next, let c_i be the letter written on the back of card i, and print those letters in the following format, followed by a newline. Here, c_i must be among the first N uppercase letters.

c_1 c_2 \cdots c_{\tbinom{2N}{N}}

Next, repeat the following process T times. The t-th iteration (1 \leq t \leq T) corresponds to the t-th magic.

Read the announced letter s given in the following format:

s

Then, for i = 1, 2, \dots, N in this order, do the following.

• Read integers a_i and b_i given in the following format:

a_i b_i

• Print the chosen position d in the following format, followed by a newline. Here, d must be a_i or b_i.

d

If your output was malformed or the previous magic failed, no more input such as s or (a_i, b_i) is given, but -1 is given from Standard Input. In this case, exit immediately. (If you fail for the first time in the T-th magic, or your output was malformed for the first time at i = N in the T-th magic, no more input follows.)

Notes

Sample Interaction

Note that this is just an example of interaction.

Problem Statement

Japan has N airports numbered 1, 2, \dots, N. AtCoder Airlines operates M directed flight routes in Japan, numbered 1, 2, \dots, M. Route j goes from airport A_j to airport B_j and costs C_j \times F yen.

Flying with AtCoder Airlines earns “miles.” You start with 0 miles. Taking route j once grants C_j miles. At airport i, you can exchange miles for money at the rate R_i yen per mile. Because of the constraint 0 \le R_i \le F-1, endless profit cycles are impossible.

You can exchange a non-integral amount of miles or have a non-integral amount of money, but you cannot have a negative amount of miles or money.

What is the minimum initial amount of money in yen needed to fly from airport 1 to airport N?

Solve \mathrm{TESTCASES} test cases.

Constraints

• 1 \le \mathrm{TESTCASES} \le 40\,000
• 2 \leq N \leq 400
• 1 \leq M \leq N \times (N-1)
• 1 \leq F \leq 100
• 1 \leq A_j \leq N
• 1 \leq B_j \leq N
• A_j \neq B_j
• (A_1, B_1), (A_2, B_2), \dots, (A_M, B_M) are all different.
• 1 \le C_j \le 100
• 0 \le R_i \le F-1
• It is possible to go from airport 1 to airport N.
• The sum of N^2 over all test cases is at most 160\,000.
• All input values are integers.

Sample Input 1

1
3 2
10
1 2 7
2 3 9
2 2 2

Sample Output 1

146

If you start with 146 yen, you can go from airport 1 to airport 3:

1. Take route 1 to go from airport 1 to airport 2. You now have 146-70=76 yen, and get 7 miles.
2. At airport 2, exchange 7 miles for 14 yen. You now have 76+14=90 yen.
3. Take route 2 to go from airport 2 to airport 3. You now have 90-90=0 yen, and get 9 miles.

If you start with less than 146 yen, you cannot go to airport 3.

Sample Input 2

1
4 4
10
1 2 7
2 4 9
2 3 1
3 2 1
2 2 9 2

Sample Output 2

106

If you start with 106 yen, you can go from airport 1 to airport 4:

1. Take route 1 to go from airport 1 to airport 2. You now have 106-70=36 yen, and get 7 miles.
2. Take route 3 to go from airport 2 to airport 3. You now have 36-10=26 yen, and get 1 mile.
3. At airport 3, exchange 8 miles for 72 yen. You now have 26+72=98 yen.
4. Take route 4 to go from airport 3 to airport 2. You now have 98-10=88 yen, and get 1 mile.
5. At airport 2, exchange 1 mile for 2 yen. You now have 88+2=90 yen.
6. Take route 2 to go from airport 2 to airport 4. You now have 90-90=0 yen, and get 9 miles.

If you start with less than 106 yen, you cannot go to airport 4.

Sample Input 3

1
7 8
100
3 2 81
3 4 42
1 6 97
4 5 42
4 1 59
6 3 34
5 3 68
2 7 47
0 58 37 10 89 16 0

Sample Output 3

16354.2758620689655172413793103448275862068965