Problem Description

You are given an $n \times n$ non-negative integer matrix $B$. You need to construct an $n \times n$ non-negative integer matrix $A$ such that:

• $A + A^\mathsf{T} = B$. Here, $A^\mathsf{T}$ denotes the transpose of $A$, which is the matrix obtained by swapping its rows and columns (the element in row $i$ and column $j$ of $A$ is located in row $j$ and column $i$ of $A^\mathsf{T}$).
• For any $i = 1,2,\cdots , n$, we have

$$\left\lfloor \frac{1}{2}\sum\limits_{j=1}^n B_{ij} \right\rfloor \le \sum\limits_{j=1}^n A_{ij} \le \left\lceil \frac{1}{2}\sum\limits_{j=1}^n B_{ij} \right\rceil$$

• For any $j = 1,2,\cdots , n$, we have

$$\left\lfloor \frac{1}{2}\sum\limits_{i=1}^n B_{ij}\right\rfloor \le \sum\limits_{i=1}^n A_{ij} \le \left\lceil \frac{1}{2}\sum\limits_{i=1}^n B_{ij} \right\rceil$$

Or report that there is no solution.

Here, $A_{ij}$ is the element in row $i$ and column $j$ of matrix $A$, and $B_{ij}$ is the element in row $i$ and column $j$ of matrix $B$.

If there are multiple solutions, you may output any one.

Input Format

This problem contains multiple test cases. The first line contains a positive integer $T$ ($1 \leq T \leq 1000$), which is the number of test cases.

Next are the descriptions of the $T$ test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 2200$), which is the size of the matrix.

The next $n$ lines each contain $n$ integers separated by spaces, describing matrix $B$. The $j$-th integer in the $i$-th line is $B_{ij}$ ($0 \leq B_{ij} \leq 10^9$).

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5 \times 10^6$.

Output Format

For each test case, if there is no solution, output one line containing only the string $\tt{No}$.

Otherwise, output $n + 1$ lines, where:

• The first line contains the string $\tt{Yes}$.
• The next $n$ lines each contain $n$ integers separated by spaces, describing the matrix $A$. The $j$-th integer in the $i$-th line is $A_{ij}$ ($0 \leq A_{ij} \leq 10^9$).

If there are multiple solutions, you may output any one.

The answer is case-insensitive. For example, $\tt{yEs}$, $\tt{Yes}$, $\tt{yes}$, and $\tt{YES}$ will all be considered as $\tt{Yes}$.

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

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

Hint

Translated by ChatGPT 5