Problem Statement

You are given N sequences of positive integers, each of length M. The i-th sequence is A_i=(A_{i,1},A_{i,2},\dots,A_{i,M}).

There are M^N ways to choose one element from each of these N sequences. Find the sum, modulo 998244353, of "the number of distinct integers among the chosen elements" over all such ways.

Constraints

• 1 \le N,M \le 500
• 1 \le A_{i,j} \le NM
• All input values are integers.

Sample Input 1

2 2
1 3
2 3

Sample Output 1

7

For example, if A_{1,1} and A_{2,1} are chosen, there are two distinct integers among the chosen elements: 1 and 2.

The number of distinct integers is 1 only when A_{1,2} and A_{2,2} are chosen, and it is 2 in the other three cases, so the answer is 7.

Sample Input 2

2 2
1 1
1 2

Sample Output 2

6

Sample Input 3

3 5
3 1 3 4 2
5 2 1 2 3
4 6 2 5 6

Sample Output 3

327

Problem Statement

There are N non-negative integers A_1,A_2,\dots,A_N written on a blackboard.

Alice and Bob play a game. Starting with Alice, they alternately perform the following operation, and the player who reduces the number of integers written on the blackboard to 0 wins.

• Let m be the minimum non-negative integer currently written on the blackboard.
  • If m > 0, choose a positive integer x between 1 and m, inclusive. Replace every integer written on the blackboard with its current value minus x.
  • If m = 0, erase one or more of the 0s written on the blackboard.

Determine who wins when both players play optimally to win.

T test cases are given; solve each of them.

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 2 \times 10^5
• 0 \le A_i \le 10^9
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

5
1
2
3
1 1 1
4
1 2 3 4
7
3 1 4 1 5 9 2
3
218 503 2026

Sample Output 1

Alice
Bob
Bob
Bob
Alice

For the first test case, one possible game progression is as follows:

• Initially, 2 is written on the blackboard.
• Alice chooses x = 1. Now 1 is written on the blackboard.
• Bob chooses x = 1. Now 0 is written on the blackboard.
• Alice chooses and erases one 0. Now nothing is written on the blackboard.

When both players play optimally to win, Alice wins.

For the second test case, one possible game progression is as follows:

• Initially, 1,1,1 are written on the blackboard.
• Alice chooses x = 1. Now 0,0,0 are written on the blackboard.
• Bob chooses and erases one 0. Now 0,0 are written on the blackboard.
• Alice chooses and erases one 0. Now 0 is written on the blackboard.
• Bob chooses and erases one 0. Now nothing is written on the blackboard.

When both players play optimally to win, Bob wins.

Problem Statement

Prepare as few types of ladder lotteries as possible and combine them so that all permutations can be produced.

This is an interactive problem (in which your program and the judge program interact via input and output).

You are given a positive integer N.

Choose any positive integer m and m permutations of (1,2,\dots,N), and output them. Let the i-th permutation be P_i=(P_{i,1},P_{i,2},\dots,P_{i,N}).

Then, a permutation Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N) is given. Output a sequence of positive integers A=(A_1,A_2,\dots,A_k) satisfying all of the following conditions.

• 0 \le k \le 2N^2
• All elements of A are between 1 and m, inclusive.
• Starting from the sequence R=(1,2,\dots,N), performing the following operation for i = 1,2,\dots,k in order results in R = Q.
• Let p = P_{A_i}. Simultaneously replace R_{j} with R_{p_j} for each j = 1,2,\dots,N.

Let m_{\min} be the minimum value of m for which the above problem can be solved regardless of Q. Your output m must equal m_{\min}.

Constraints

• 3 \le N \le 500
• Q is a permutation of (1,2,\dots,N).
• All input values are integers.

Input/Output

This is an interactive problem (in which your program and the judge program interact via input and output).

First, the judge gives you a positive integer N in the following format:

N

Then, output your chosen positive integer m and m permutations of (1,2,\dots,N) in the following format over m+1 lines. Here, the j-th element of the i-th permutation is P_{i,j}. Be sure to output a newline at the end.

m
P_{1,1}\ P_{1,2}\ \dots\ P_{1,N}
P_{2,1}\ P_{2,2}\ \dots\ P_{2,N}
\vdots
P_{m,1}\ P_{m,2}\ \dots\ P_{m,N}

The following conditions must be satisfied:

• m \le 1000
• (P_{i,1},P_{i,2},\dots,P_{i,N}) is a permutation of (1,2,\dots,N).

If your output P does not satisfy the above conditions, the judge outputs -1. At that point, your submission has already been judged as incorrect. The judge program terminates at that point, so it is advisable for your program to terminate as well.

Then, the judge gives you a permutation Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N) in the following format:

Q_1\ Q_2\ \dots\ Q_N

Then, output a sequence of positive integers A=(A_1,A_2,\dots,A_k) in the following format. Be sure to output a newline at the end.

k\ A_1\ A_2\ \dots\ A_k

Your output is judged as correct if and only if the following conditions are all satisfied:

• m = m_{\min}
• 0 \le k \le 2N^2
• All elements of A are between 1 and m, inclusive.
• Starting from the sequence R=(1,2,\dots,N), performing the following operation for i = 1,2,\dots,k in order results in R = Q.
• Let p = P_{A_i}. Simultaneously replace R_{j} with R_{p_j} for each j = 1,2,\dots,N.

Notes

• After each output, insert a newline and flush the standard output. Failure to do so may result in a judge verdict of TLE.
• If you receive -1, terminate your program immediately. If you do, the judge verdict will be WA, but if you do not, the judge verdict will be indeterminate.
• Terminate your program immediately after outputting your answer as well. Otherwise, the judge verdict will be indeterminate.
• Do not output unnecessary newlines, as they will be considered malformatted.
• The judge for this problem is not adaptive. The judge program determines Q before the interaction begins.

Sample Input/Output

The following is a case with N=3,Q=(2,3,1).

Problem Statement

You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).

For a sequence of integers x=(x_1,x_2,\dots,x_k), define the score of x as the number of indices i satisfying x_i < x_{i+1}.

Process the following query Q times.

• You are given positive integers l and r with 1 \le l \le r \le N. For X = (P_l,P_{l+1},\dots,P_r), solve the following problem.
  • Let M be the maximum score of a non-empty subsequence of X. Find the minimum length of a non-empty subsequence of X whose score equals M.

Constraints

• 1 \le N,Q \le 2 \times 10^5
• P is a permutation of (1,2,\dots,N).
• 1 \le l \le r \le N
• All input values are integers.

Sample Input 1

6 4
2 1 4 6 3 5
1 3
3 6
2 2
1 6

Sample Output 1

2
4
1
5

For the first query, X = (2,1,4). The maximum score M = 1 is achieved by (2,4),(1,4),(2,1,4). The minimum length among these is 2, achieved by (2,4),(1,4).

For the second query, X = (4,6,3,5) and M = 2. (4,6,3,5) achieves the minimum length 4 among those with score 2.

For the third query, X = (1) and M = 0. (1) achieves the minimum length 1 with score 0.

For the fourth query, X = (2,1,4,6,3,5) and M = 3. (2,4,6,3,5) achieves the minimum length 5 with score 3.

Sample Input 2

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

Sample Output 2

2
2
2
4
5
7
2
5

Problem Statement

For a permutation p=(p_1,p_2,\dots,p_N) of (1,2,\dots,N) and a positive integer M, let f(p,M) denote the answer to the following problem.

Perform the following operation M times on p.

• Choose an integer i with 1 \le i \le N-1, and reverse each of (p_1,p_2,\dots,p_i) and (p_{i+1},p_{i+2},\dots,p_N). Formally, replace p with (p_i,p_{i-1},\dots,p_1,p_N,p_{N-1},\dots,p_{i+1}).

There are (N-1)^M possible sequences of operations. Find the sum, modulo 998244353, of "the number of inversions of p after M operations" over all such sequences.

You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N). Process the following query Q times.

• You are given an integer x with 1 \le x \le N-1 and a positive integer K. Swap P_x and P_{x+1}. Then, find f(P,K).

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• P is a permutation of (1,2,\dots,N).
• 1 \le x \le N-1
• 1 \le K \le 10^9
• All input values are integers.

Sample Input 1

3 2
1 3 2
1 1
2 1

Sample Output 1

4
4

For the first query, swapping P_1 and P_2 gives P=(3,1,2). There are two possible sequences of operations as follows:

• Choose i = 1. P becomes (3,2,1). The number of inversions is 3.
• Choose i = 2. P becomes (1,3,2). The number of inversions is 1.

Thus, the answer is 3+1=4.

For the second query, swapping P_2 and P_3 gives P=(3,2,1). There are two possible sequences of operations as follows:

• Choose i = 1. P becomes (3,1,2). The number of inversions is 2.
• Choose i = 2. P becomes (2,3,1). The number of inversions is 2.

Thus, the answer is 2+2=4.

Sample Input 2

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

Sample Output 2

11
28
67
242

Sample Input 3

10 7
7 9 3 10 5 2 4 6 8 1
2 29
1 86
3 30
8 64
1 24
1 9
5 55

Sample Output 3

29362950
633265500
847469581
741165544
385334408
653522086
169485402

Problem Statement

Problems F and F2 are the same problem with different constraints on M. In Problem F, 1 \le M \le 4.

You are given a positive integer M. Consider the following problem.

Bucket

You are given a positive integer N and non-negative integer sequences A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N) of length N. All elements of A and B are between 0 and M, inclusive.

There are N buckets numbered 1 to N. Each bucket can hold up to M liters of water. Initially, bucket i contains A_i liters of water.

You may perform the following operation any number of times.

• Choose two distinct buckets i and j. Continue pouring water from bucket i into bucket j as long as both of the following conditions are satisfied:
  • Bucket i still has water remaining.
  • The amount of water in bucket j is less than M liters.

Your goal is to have exactly B_i liters of water in bucket i for all i. Determine whether the goal can be achieved.

You are given a non-negative integer matrix X=(X_{i,j})(0 \le i,j \le M) of (M+1) rows and (M+1) columns. Process the following queries Q times.

• You are given non-negative integers i,j,Y with 0 \le i,j \le M. Change X_{i,j} to Y. Then, obtain non-negative integer sequences A and B by the following procedure.
  • Initialize non-negative integer sequences A and B as empty sequences.
  • For i = 0,1,\dots,M in this order:
  • For j = 0,1,\dots,M in this order:
  • Do this X_{i,j} times: append i to the end of A and j to the end of B.
• Solve Bucket for the non-negative integer sequences A and B of length N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}.

Constraints

• 1 \le M \le 4
• 1 \le Q \le 10^6
• 0 \le X_{i,j},Y \le 10^{17}
• 0 \le i,j \le M
• \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} \ge 1 at any time.
• All input values are integers.

Sample Input 1

3 3
0 0 0 0
0 0 2 0
1 0 0 0
0 0 0 0
0 0 0
2 3 1
2 1 1

Sample Output 1

Yes
No
Yes

The first query makes X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} , and we obtain A=(1,1,2),B=(2,2,0).

In this case, the goal can be achieved by the following sequence of operations, for example.

• Set i = 1,j = 2. The amount of water in each bucket changes from (1,1,2) to (0,2,2).
• Set i = 3,j = 1. The amount of water in each bucket changes from (0,2,2) to (2,2,0).

The second query makes X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} , and we obtain A=(1,1,2,2),B=(2,2,0,3).

In this case, the goal cannot be achieved no matter how operations are performed.

The third query makes X=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} , and we obtain A=(1,1,2,2,2),B=(2,2,0,1,3).

In this case, the goal can be achieved by the following sequence of operations, for example.

• Set i = 1,j = 2. The amount of water in each bucket changes from (1,1,2,2,2) to (0,2,2,2,2).
• Set i = 3,j = 1. The amount of water in each bucket changes from (0,2,2,2,2) to (2,2,0,2,2).
• Set i = 4,j = 5. The amount of water in each bucket changes from (2,2,0,2,2) to (2,2,0,1,3).

Sample Input 2

4 10
45636788580181785 16131322312654301 43477244591521823 6505049084010674 86530627327096446
95921187347997793 55491565467039163 87684565747362311 80318628430974482 12308092878301956
75570615154690027 96403707363045776 14150012766408204 6612197700307407 64417022692908525
5530468643826479 41731276604630756 15675296751519388 59461896803210859 66666666666666666
72767956047192820 18258893791516726 58852629621892634 33333333333333333 29923985408775019
2 1 26541245644686826
2 4 29485791833729050
4 1 21832826336874318
3 2 4953499115446612
2 0 69217973349997921
2 4 23133150029036944
3 4 55834224798559242
1 2 98517007615469735
2 3 3768060024403703
0 4 87241661746072372

Sample Output 2

No
Yes
No
Yes
No
Yes
No
No
No
No

Problem Statement

Problems F and F2 are the same problem with different constraints on M. In Problem F2, M = 5.

You are given a positive integer M. Consider the following problem.

Bucket

You are given a positive integer N and non-negative integer sequences A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N) of length N. All elements of A and B are between 0 and M, inclusive.

There are N buckets numbered 1 to N. Each bucket can hold up to M liters of water. Initially, bucket i contains A_i liters of water.

You may perform the following operation any number of times.

• Choose two distinct buckets i and j. Continue pouring water from bucket i into bucket j as long as both of the following conditions are satisfied:
  • Bucket i still has water remaining.
  • The amount of water in bucket j is less than M liters.

Your goal is to have exactly B_i liters of water in bucket i for all i. Determine whether the goal can be achieved.

You are given a non-negative integer matrix X=(X_{i,j})(0 \le i,j \le M) of (M+1) rows and (M+1) columns. Process the following queries Q times.

• You are given non-negative integers i,j,Y with 0 \le i,j \le M. Change X_{i,j} to Y. Then, obtain non-negative integer sequences A and B by the following procedure.
  • Initialize non-negative integer sequences A and B as empty sequences.
  • For i = 0,1,\dots,M in this order:
  • For j = 0,1,\dots,M in this order:
  • Do this X_{i,j} times: append i to the end of A and j to the end of B.
• Solve Bucket for the non-negative integer sequences A and B of length N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}.

Constraints

• M = 5
• 1 \le Q \le 10^6
• 0 \le X_{i,j},Y \le 10^{17}
• 0 \le i,j \le M
• \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} \ge 1 at any time.
• All input values are integers.

Sample Input 1

5 3
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 5 0
4 0 1
1 5 1

Sample Output 1

Yes
No
Yes

The sequences A and B obtained at each query are as follows:

• At the time of processing the first query: A=(0,3,3),B=(0,1,5)
• At the time of processing the second query: A=(0,3,3,4),B=(0,1,5,0)
• At the time of processing the third query: A=(0,1,3,3,4),B=(0,5,1,5,0)

Sample Input 2

5 10
61717749303507807 83849626163233111 84388501405824055 8514730661576685 8408052512772637 42085112989954358
33333333333333333 70477132070314067 43546706335438313 61370380435458585 99101823689638606 77669930608921552
33333333333333333 21459633523757247 8151410984806542 14183403125185219 68299186110683565 35549692732468863
98146856836553017 53630682913685434 12400422817799555 29967281381593348 67521547136428867 48353536740933612
97356055491517734 55777507072845580 59235925940735000 6228770338558507 41778108608223669 60544364859700647
5960356361755846 59147828067221624 65687376011190687 33333333333333333 31563848832259443 98724011871535047
2 3 1333175914347793
3 4 80371774347266293
2 1 20920094361040152
2 3 793636751630698
0 5 68209364995103050
2 0 98643963346205063
3 2 7931291059115265
0 1 79380494404548821
2 5 6440038070576840
2 3 88122600737306767

Sample Output 2

No
No
No
No
No
Yes
No
Yes
No
Yes