Problem Statement

You are given strings X and Y of length N consisting of A and B. Let X_i denote the i-th character of X.

Determine whether it is possible to make X equal to Y by performing the following operation between 0 and \left\lfloor \frac{N}{2} \right\rfloor times, inclusive.

• Choose a pair of integers (l, r) such that 1\leq l < r \leq N, X_l= A, and X_r= B. Reverse the elements of X from the l-th to the r-th position. Here, "reversing the elements of X from the l-th to the r-th position" means simultaneously replacing X_l,X_{l+1},\ldots,X_{r-1},X_r with X_r,X_{r-1},\ldots,X_{l+1},X_l.

If it is possible to make X equal to Y, output one such sequence of operations.

T test cases are given; solve each of them.

Constraints

• 1 \leq T \leq 2.5\times 10^5
• 2 \leq N \leq 5\times 10^5
• The sum of N over all test cases is at most 5\times 10^5.
• X and Y are strings of length N consisting of A and B.
• All input values are integers.

Sample Input 1

3
5
ABAAB
ABBAA
4
AAAA
BBBB
10
BABBAABBAA
BBBBAAABAA

Sample Output 1

Yes
1
3 5
No
Yes
3
2 7
4 6
3 5

In the first test case, X_3= A and X_5= B, so we can perform the operation of reversing the elements of X from the 3-rd to the 5-th position. After this operation, X is ABBAA, which equals Y.

In the second test case, it is impossible to make X equal to Y regardless of the operations performed.

Problem Statement

You are given positive integers N and K.

There is a complete bipartite graph G with N vertices l_1, l_2, \ldots, l_N on the left and N vertices r_1, r_2, \ldots, r_N on the right. It has N^2 edges; for each (i, j)\ (1\leq i\leq N, 1\leq j\leq N), there is one undirected edge between vertices l_i and r_j.

Determine whether there exists a way to write an integer between 1 and N^2, inclusive, on each edge of G (where the N^2 integers written are all distinct) such that the answer to the following problem is K, and if such a way exists, find one.

Among all walks on graph G, we call a walk good if the sequence of numbers written on the edges traversed, in the order they are traversed, is strictly increasing.

Find the maximum number of edges contained in a good walk.

T test cases are given; solve each of them.

Constraints

• 1\leq T\leq 3000
• 1\leq N\leq 700
• 1\leq K\leq N^2
• The sum of N^2 in each input is at most 5\times 10^5.
• All input values are integers.

Sample Input 1

3
2 1
2 3
3 5

Sample Output 1

No
Yes
1 2
3 4
Yes
2 9 7
4 5 6
1 8 3

For the first test case, no valid way of writing exists.

For the second test case, a good walk containing three edges is r_1 \xrightarrow{1} l_1 \xrightarrow{2}r_2\xrightarrow{4}l_2. No good walk contains four or more edges, so this output satisfies the condition.

For the third test case, a good walk containing five edges is l_1 \xrightarrow{2} r_1 \xrightarrow{4}l_2\xrightarrow{6}r_3 \xrightarrow{7} l_1 \xrightarrow{9} r_2. No good walk contains six or more edges, so this output satisfies the condition.

Problem Statement

There is a simple directed graph G with N vertices and M edges. The vertices are numbered 1 through N, and the i-th edge goes from vertex a_i to vertex b_i. It is guaranteed that (a_i,b_i)\neq (b_j,a_j) for i\neq j. Also, an integer K with 2 \leq K \leq N-2 is given.

Determine whether it is possible to make G a graph with no directed cycles (DAG) by performing the following operation zero or more times.

• Choose a size-K subset S of \lbrace 1,\ldots,N\rbrace. For every directed edge whose both endpoints' numbers are in S, reverse its direction.
  • That is, if there is an edge from vertex u to vertex v\ (u,v\in S), delete that edge and add a directed edge from vertex v to vertex u. This operation is performed simultaneously for all applicable edges.

T test cases are given; solve each of them.

Constraints

• 1 \leq T \leq 50000
• 4 \leq N \leq 2\times 10^5
• 0 \leq M \leq \min({N(N-1), 2\times 10^5})
• 2 \leq K \leq N-2
• 1 \leq a_i, b_i \leq N
• a_i \neq b_i
• (a_i, b_i) \neq (a_j, b_j) and (a_i,b_i) \neq (b_j,a_j) for i\neq j.
• The sum of N in each input is at most 2\times 10^5.
• The sum of M in each input is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes

In the first test case, G can be made into a graph with no directed cycles by performing the following two operations.

• In the first operation, perform the operation with S = \lbrace 1, 2,7 \rbrace. The directed edges whose both endpoints' numbers are in S are the edge from vertex 1 to vertex 2 and the edge from vertex 7 to vertex 1. The directions of these edges are reversed.

• In the second operation, perform the operation with S = \lbrace 4, 5,7 \rbrace. The directed edge whose both endpoints' numbers are in S is the edge from vertex 4 to vertex 5. The direction of this edge is reversed, and G becomes a graph with no directed cycles.

In the second test case, it is impossible to make G a graph with no directed cycles regardless of the operations performed.

Problem Statement

You are given a positive integer N and a prime P.

There is a sequence A=(A_1,A_2,\ldots,A_N) of length N where all elements are 0.

You can repeat the following operation zero or more times.

• Choose a pair of integers (l, r)\ (1\leq l\leq r\leq N). Replace each of A_l,A_{l+1},\ldots,A_r with \dfrac{r(r-1)}{2}+l.

Find the number, modulo P, of sequences that can be obtained as A after performing operations.

Constraints

• 1\leq N\leq 5000
• P is a prime satisfying 10^8\lt P\lt 10^9.
• All input values are integers.

Sample Input 1

1 998244353

Sample Output 1

2

The two possible sequences A are (0) and (1).

Sample Input 2

2 998244353

Sample Output 2

7

The seven possible sequences A are (0,0),(0,3),(1,0),(1,2),(1,3),(2,2),(2,3).

Sample Input 3

3 998244353

Sample Output 3

38

Sample Input 4

4 998244353

Sample Output 4

282

Sample Input 5

77 777777773

Sample Output 5

112061248

Problem Statement

Consider writing 0 or 1 on each vertex of a 4\times 500 grid graph. Write the values cleverly so that for each N=0,1,\ldots,999899,999900, the following condition is satisfied.

• There exists a Hamiltonian path on the grid graph such that the sequence of numbers written on the vertices along the path has an inversion count of N.

An example with 3\times 4. With this assignment, N = 10, 11, \ldots, 20 are achievable.

This is an interactive problem. The parameters in the problem statement are fixed at H=4,W=500,Q=200.

You and the judge perform the following steps. The steps consist of Phase 1 and Phase 2; Phase 1 is performed first, immediately followed by Phase 2.

(Phase 1)

Output an H\times W matrix A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W) where each element is 0 or 1.

(Phase 2)

Solve the following problem Q times.

The judge gives you an integer N.
Consider an H-row W-column grid. The cell (i,j), located at the i-th row from the top and the j-th column from the left, has the integer A_{i,j} written on it.
Find a path P of length HW that starts at any cell, moves to an adjacent cell (up, down, left, or right) repeatedly, visits all HW cells exactly once, and ends at any cell, such that the following is satisfied.

• The inversion count of the sequence of length HW obtained by listing the integers written on the cells visited by P in order is N.

Constraints

• H=4,W=500,Q=200
• 0\leq N\leq 999900
• All input values are integers.

Interaction

This is an interactive problem.

First, H,W,Q are given from Standard Input.

H W Q

(Phase 1)

Output an H\times W matrix A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W) where each element is 0 or 1, over H lines.

The i-th line should contain A_{i,1}A_{i,2}\ldots A_{i,W} as a string of length W consisting of 0 and 1.

A_{1,1}A_{1,2}\ldots A_{1,W}
A_{2,1}A_{2,2}\ldots A_{2,W}
\vdots
A_{H,1}A_{H,2}\ldots A_{H,W}

(Phase 2)

Solve the problem Q times. For each problem, first an integer N is given from Standard Input.

N

(Note: if your answer to the previous problem was incorrect, or if A or the path was output in an incorrect format, then instead of N, -1 is given from Standard Input here. In that case, immediately terminate the program normally. However, if an incorrect output is given for the first time in the Q-th problem, no further input will be given.)

Then, output a path P satisfying the condition, where the i-th visited cell is (x_i, y_i), in the following format:

x_1 y_1
x_2 y_2
\vdots
x_{HW} y_{HW}

x_i and y_i must satisfy the following.

• 1\leq x_i\leq H, 1\leq y_i\leq W.
• (x_i,y_i)\neq (x_j,y_j) if i\neq j.
• |x_i-x_{i+1}|+|y_i-y_{i+1}|=1 for i=1,2,\ldots,HW-1.
• The inversion count of the sequence (A_{x_1,y_1}, A_{x_2,y_2},\ldots,A_{x_{HW},y_{HW}}) is N.

Notes

• If you receive -1 as input from the judge, immediately terminate the program normally. If you terminate, the verdict will be WA; otherwise, the verdict is indeterminate.
• In each output, include a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.
• Extra newlines in output are considered as malformed; do not include them.
• Terminate your program immediately after finishing Phase 2. Otherwise, the verdict is indeterminate.

Sample Interaction

Below is a sample interaction for the case H=3,W=4,Q=2.

This example does not satisfy the constraints and is not included in the judge.

3 4 2

1101
0110
1010

10

3 2
3 3
3 4
2 4
1 4
1 3
2 3
2 2
1 2
1 1
2 1
3 1

15

1 1
2 1
3 1
3 2
3 3
3 4
2 4
2 3
2 2
1 2
1 3
1 4

Problem Statement

There are N jobs numbered 1 through N, and you want to complete them over N days. You perform exactly one job per day.

Job i can be performed on any day from day L_i through day R_i. Here, the following conditions are guaranteed to hold for L_i and R_i:

• 1 \leq L_i \leq i \leq R_i \leq N
• 1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N
• 1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N

Particularly, from the first condition, it follows that it is possible to complete all N jobs over N days.

Furthermore, each job has a type of L or R. Initially, all jobs are of type R.

The cost of performing a job is defined as follows:

• Suppose job i is performed on day x_i. If job i is of type L, the cost is defined as x_i-L_i; if it is of type R, the cost is defined as R_i-x_i.

From now on, there will be N queries that change the type of a job to L. In the i-th query, the type of job P_i is changed to L.

For each k=0,1,\ldots,N, solve the following problem:

• Consider the state after processing the first k queries. Find the minimum possible total cost of all N jobs.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq L_i \leq i \leq R_i \leq N
• 1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N
• 1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N
• (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

3
1 3
1 3
2 3
2 1 3

Sample Output 1

3 1 1 2

An optimal schedule for each k is as follows:

• k=0: Perform jobs 1,2,3 on days 1,2,3 respectively. The total cost is (3-1)+(3-2)+(3-3)=3.
• k=1: Perform jobs 1,2,3 on days 2,1,3 respectively. The total cost is (3-2)+(1-1)+(3-3)=1.
• k=2: Perform jobs 1,2,3 on days 1,2,3 respectively. The total cost is (1-1)+(2-1)+(3-3)=1.
• k=3: Perform jobs 1,2,3 on days 1,2,3 respectively. The total cost is (1-1)+(2-1)+(3-2)=2.

Sample Input 2

4
1 4
2 4
3 4
4 4
1 2 3 4

Sample Output 2

6 3 1 0 0

Sample Input 3

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

Sample Output 3

17 13 10 11 7 3 6 10 14

Sample Input 4

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

Sample Output 4

44 41 37 29 22 16 12 11 16 20 21 27 35 39 42 49