Problem Statement

You are given an N\times N matrix A=(A_{i,j})\ (1\leq i,j\leq N) and integer sequences of length N: R=(R_1,R_2,\ldots,R_N), C=(C_1,C_2,\ldots,C_N). Each element of A is 0 or 1, and each element of R,C is at least 0 and less than \frac{N}{4}.

You can freely choose a pair of strings X,Y of length N consisting of 0 and 1. Based on the chosen strings X,Y, perform the following operations:

• First, for each i=1,2,\ldots,N, do the following. Let X_i be the i-th character of X:
  • If X_i is 0, do nothing.
  • If X_i is 1, flip all elements in the i-th row of A. That is, for each j=1,2,\ldots,N, replace A_{i,j} with 1-A_{i,j}.
• Next, for each j=1,2,\ldots,N, do the following. Let Y_j be the j-th character of Y:
  • If Y_j is 0, do nothing.
  • If Y_j is 1, flip all elements in the j-th column of A. That is, for each i=1,2,\ldots,N, replace A_{i,j} with 1-A_{i,j}.

Determine whether it is possible to choose X,Y cleverly so that the matrix A after the operations satisfies the following conditions, and if possible, output one such pair.

• For each i=1,2,\ldots,N, the sum of elements in the i-th row of A, \displaystyle \sum_{j=1}^N A_{i,j}, is R_i.
• For each j=1,2,\ldots,N, the sum of elements in the j-th column of A, \displaystyle \sum_{i=1}^N A_{i,j}, is C_j.

You are given T test cases, so answer each of them.

Constraints

• 1\leq T\leq 10^5
• 1\leq N\leq 1000
• A_{i,j} \in\lbrace 0,1\rbrace
• 0\leq R_i,C_j\lt \frac{N}{4}
• T,N,R_i,C_j are integers.
• The sum of N^2 over all test cases in one input file is at most 10^6.

Sample Input 1

3
2
10
01
0 0
0 0
5
10101
11110
01111
10011
00110
1 1 1 1 1
1 1 1 1 1
10
0001011010
0101101000
0000101111
0010011100
0111000001
0011100110
1110001110
1100110000
0110111011
1101101101
1 1 0 2 0 0 2 2 2 2
2 2 0 1 0 2 1 2 1 1

Sample Output 1

Yes
01
10
Yes
01101
10001
No

For the first test case, A=\begin{pmatrix}1&0 \\ 0&1\end{pmatrix}. Consider the case where X,Y are 01 and 10, respectively. The operations are performed as follows:

• X_1 is 0, so do nothing.
• X_2 is 1, so flip the elements in the 2nd row of A, resulting in A=\begin{pmatrix}1&0 \\ 1&0\end{pmatrix}.
• Y_1 is 1, so flip the elements in the 1st column of A, resulting in A=\begin{pmatrix}0&0 \\ 0&0\end{pmatrix}.
• Y_2 is 0, so do nothing.

Therefore, the matrix A after the operations is A=\begin{pmatrix}0&0 \\ 0&0\end{pmatrix}. The sum of elements in the 1st row, the sum of elements in the 2nd row, the sum of elements in the 1st column, and the sum of elements in the 2nd column are all 0, so the conditions are satisfied.

It would also be correct to output:

Yes
10
01

Problem Statement

You are given a sequence of non-negative integers of length N: A=(A_1,A_2,\ldots,A_N) and a non-negative integer K.

Determine whether it is possible to make A_1=K by performing the following operation at most 10^4 times:

• Choose an integer i\ (1\leq i\leq N-1). Let x=A_i\oplus A_{i+1}, then replace both A_i,A_{i+1} with x.

Here, \oplus denotes the bitwise XOR operation.

If possible, output one such sequence of operations.

You are given T test cases, so solve each of them.

Constraints

• 1\leq T\leq 50
• 3\leq N\leq 60
• 0\leq A_i,K\lt 2^{60}
• All input values are integers.

Sample Input 1

5
3 5
2 3 4
3 0
2 3 4
3 8
2 3 4
3 2
2 3 4
4 10
2 3 4 8

Sample Output 1

Yes
2
2 1
Yes
3
1 1 1
No
Yes
0

Yes
4
2 3 2 1

For the first test case, you can make A_1=5 by performing the operations as follows:

1. Choose i=2. A becomes (2,7,7).
2. Choose i=1. A becomes (5,5,7).

For the second test case, you can make A_1=0 by performing the operations as follows:

1. Choose i=1. A becomes (1,1,4).
2. Choose i=1. A becomes (0,0,4).
3. Choose i=1. A becomes (0,0,4).

For the third test case, it is impossible to make A_1=8 with at most 10^4 operations.

Problem Statement

In this problem, we simply call a tree with N vertices numbered 1,2,\ldots,N and unnumbered edges an N-vertex tree.

When an N-vertex tree T and a permutation Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,N) satisfy the following condition, the permutation Q is called a good permutation of tree T:

There are N points 1,2,\ldots,N arranged counterclockwise at equal intervals on a circle in this order. For each edge \lbrace u,v\rbrace of tree T, draw a line segment connecting the two points Q_u,Q_v. Then, among the N-1 line segments drawn, no two of them have a common point except at their endpoints.

You are given M permutations of (1,2,\ldots,N): P^1=(P^1_1,P^1_2,\ldots,P^1_N),P^2=(P^2_1,P^2_2,\ldots,P^2_N),\ldots,P^M=(P^M_1,P^M_2,\ldots,P^M_N).

Find the number, modulo 998244353, of N-vertex trees such that P^1,P^2,\ldots,P^M are all good permutations.

Constraints

• 2\leq N,M\leq 500
• P^1,P^2,\ldots,P^M are permutations of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

4 2
1 4 2 3
3 1 4 2

Sample Output 1

8

For example, for the following two trees, both P^1,P^2 are good permutations. (The blue numbers represent vertex numbers.)

On the other hand, for the following tree, P^2 is not a good permutation.

There are 8 four-vertex trees in total such that both P^1,P^2 are good permutations.

Sample Input 2

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

Sample Output 2

540

Problem Statement

You are given positive integers H,W.

There is an H \times W matrix A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W), where initially all elements are 0.

You can perform the following two types of operations on this matrix in any order and any number of times:

• Choose integers r,c\ (1\leq r\leq H,1\leq c\leq W). Set all of A_{r,1},A_{r,2},\ldots,A_{r,c} to 1.
• Choose integers r,c\ (1\leq r\leq H,1\leq c\leq W). Set all of A_{1,c},A_{2,c},\ldots,A_{r,c} to 1.

Find the sum of \displaystyle \sum_{i=1}^H\sum_{j=1}^W A_{i,j} over all matrices that can be obtained by repeating the above operations, modulo 998244353.

Constraints

• 1\leq H,W
• HW\leq 2\times 10^5
• All input values are integers.

Sample Input 1

2 2

Sample Output 1

29

There are 14 matrices that can be obtained by repeating the operations:

The answer is 0+1+1+2+1+2+2+3+2+3+2+3+3+4=29.

\begin{pmatrix}0&0 \\ 0&1\end{pmatrix} and \begin{pmatrix}1&0 \\ 0&1\end{pmatrix} cannot be obtained by any sequence of operations.

Sample Input 2

1 10

Sample Output 2

5120

Sample Input 3

123 456

Sample Output 3

428623282