题目描述

Yoimiya 有一个 $n\times m$ 的矩阵 $A$。$A$ 中的每个元素都是 $[0,10^5]$ 中的非负整数。

她用这个矩阵 $A$ 生成了一个 $n\times m$ 的矩阵 $E=f(A)$，其中 $E_{i,j}$ 的值为 $A$ 中每个位置到 $(i,j)$ 的曼哈顿距离乘上这个位置的权值之和。

形式化地，有

$$E_{i,j}=\sum_{1\le x\le n}\sum_{1\le y\le m}(|x-i|+|y-j|)A_{x,y} $$

现在，Yoimiya 丢失了原本的矩阵 $A$，她希望你用矩阵 $E=f(A)$ 还原出一个符合上述条件的 $A$。如果有多解，输出任意一组即可。

注意尽管实际的矩阵 $A$ 中每个元素均在 $[0,10^5]$ 内，但 Yoimiya 并不要求你还原出的 $A$ 中的元素 $\le 10^5$。她只要求你还原出的 $A$ 中的每个元素均为 $\le 10^{16}$ 非负整数。

输入格式

本题有多组数据。 第一行输入一个正整数 $T$ 表示数据组数。对于每组数据：

第一行两个正整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个整数，第 $i+1$ 行的第 $j$ 个数为 $E_{i,j}$。

输出格式

对于每组数据，输出一个 $n\times m$ 的矩阵表示你构造的 $A$ 矩阵。请保证你构造的矩阵中，元素 $\le 10^{16}$。

样例 $1$ 输入

3
1 2
1 1
6 6
43 34 25 24 33 42
42 33 24 23 32 41
41 32 23 22 31 40
40 31 22 21 30 39
39 30 21 20 29 38
48 39 30 29 38 47
2 2
400000 400000
400000 400000

样例 $1$ 输出

1 1
0 0 4 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 5 0 0
0 0 0 0 0 0
200000 0
0 200000

样例 $1$ 解释

不难验证给出的矩阵符合条件。

尽管第三组数据中，答案给出的构造中存在 $A_{i,j}>10^5$（因而不可能是 Yoimiya 一开始拥有的矩阵 $A$），但每个数都是非负整数，因此仍然是合法的。

样例 $2,3,4$

见附加文件中的 rapieres2/3/4.in 与 rapieres2/3/4.ans。

每个样例中均有 $8$ 组数据，其中前 $6$ 组数据分别满足特殊性质 AB,AC,BC,A,B,C，第 $7,8$ 组数据可能不满足任何特殊性质。

此外，样例 $2$ 满足 $\sum n,\sum m\le 50$，样例 $3$ 满足 $\sum n,\sum m\le 200$，样例 $4$ 满足 $\sum n,\sum m\le 3000$。

附加文件下载

校验器

为了方便选手测试，在附件中我们下发了 checker.cpp 文件与 testlib.h 目录，选手可以在 testlib.h 的同一目录下编译该程序，并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。

编译命令为：g++ checker.cpp −o checker -std=c++14。

checker 的使用方式为：checker <inputfile> <outputfile> <answerfile>，参数依次表示输入文件，你的输出文件，以及答案输出文件。

若你的输出与输出格式不符，则校验器会给出相应提示。若你的输出格式正确，但方案错误，则校验器会给出简要的错误信息。具体来说，设你给出的矩阵为 $B$，设 $E'=f(B)$，校验器会给出任意一个 $(i,j)$ 满足 $E_{i,j}\neq E'_{i,j}$。若你的方案正确，校验器会给出 ok。

数据范围与约束

对于所有数据，$1\le \sum n,\sum m\le 3000,1\le T\le 3000,0\le E_{i,j}\le 10^{16}$。

本题共有 $20$ 个测试点，每个测试点 $5$ 分。每个测试点的具体限制如下：

测试点编号	$\sum n,\sum m\le$	特殊性质
$1\sim 3$	$4$	B
$4$	$50$	AB
$5$		A
$6$		BC
$7$		B
$8$		无
$9$
$10$	$200$	BC
$11$		B
$12\sim 14$		C
$15\sim 17$		无
$18\sim 20$	$3000$

• 特殊性质 A：存在一组解 $A$ 满足所有的 $A_{i,j}$ 均相等。
• 特殊性质 B：存在一组 $A_{i,j}\in\{0,1\}$ 的解。
• 特殊性质 C：$n=1$。