题目描述

给定一个 $n\times n$ 的非负整数矩阵 $B$。你需要构造一个 $n\times n$ 的非负整数矩阵 $A$，满足：

• $A+A^\mathsf{T} = B$。其中 $A^\mathsf{T}$ 表示 $A$ 的转置，即将其行和列互换得到的新矩阵（原来 $A$ 中第 $i$ 行第 $j$ 列的元素，在 $A^\mathsf{T}$ 中位于第 $j$ 行第 $i$ 列）。
• 对于任意 $i = 1,2,\cdots , n$，都有

$$\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$$

• 对于任意 $j = 1,2,\cdots , n$，都有

$$\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$$

或报告无解。

其中，$A_{ij}$ 为矩阵 $A$ 第 $i$ 行第 $j$ 列的元素，$B_{ij}$ 为矩阵 $B$ 第 $i$ 行第 $j$ 列的元素。

如果存在多个解，输出任意一个即可。

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1 \leq T \leq 1000$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n \le 2200$），表示矩阵的大小。

接下来 $n$ 行，每行 $n$ 个整数，用一个空格分隔，描述矩阵 $B$，其中第 $i$ 行第 $j$ 个整数表示 $B_{ij}$（$0 \leq B_{ij} \leq 10^9$）。

保证所有测试用例中 $n^2$ 的总和不超过 $5 \times 10^6$。

输出格式

对于每个测试用例，若无解，输出一行，仅包含一个字符串 $\tt{No}$。

否则，输出 $n+1$ 行，其中：

• 第一行包含一个字符串 $\tt{Yes}$；
• 接下来 $n$ 行，每行包含 $n$ 个整数，用一个空格分隔，描述你构造的矩阵 $A$，其中第 $i$ 行第 $j$ 个整数表示 $A_{ij}$（$0 \leq A_{ij} \leq 10^9$）。

如果存在多个解，输出任意一个即可。

答案对大小写不敏感。例如 $\tt{yEs}$，$\tt{Yes}$，$\tt{yes}$ 和 $\tt{YES}$ 都会被视为 $\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