题目内容

一位数字艺术家正在创作一幅像素画，画布由 n 行 m 列的格子组成。第 i 行第 j 列的格子初始装有 $c_{i,j}$ 克颜料。

他可以任意移动颜料：从任意格子取出若干克颜料放到另一个格子中，但每个格子中的颜料量必须保持非负整数，且所有格子的颜料总量不变。

艺术家希望最终画布同时满足以下两个对称条件：

• 关于水平中轴线对称：对于所有 $1 \le i \le n, 1 \le j \le m$，有 $X_{i,j} = X_{n+1-i, j}$；
• 关于垂直中轴线对称：对于所有 $1 \le i \le n, 1 \le j \le m$，有 $X_{i,j} = X_{i, m+1-j}$。

其中 $X_{i,j}$ 表示最终第 i 行第 j 列的颜料克数。

请你判断是否存在一种合法的颜料分配方案，如果存在，请给出任意一种最终分布；否则指出不可能。

约束条件：

• 测试数据组数 $T$ 满足 $1 \le T \le 10^5$。
• 每组数据中，行数 $n$ 和列数 $m$ 满足 $1 \le n, m \le 2 \times 10^5$，初始颜料克数 $c_{i,j}$ 满足 $0 \le c_{i,j} \le 10^9$。
• 保证单个测试点内所有数据的 $n \times m$ 之和不超过 $5 \times 10^5$。

输入描述

第一行包含一个整数 T，表示测试数据组数。 接下来每组数据按以下格式给出： 第一行包含两个整数 n 和 m，分别表示画布的行数和列数。 接下来 n 行，每行包含 m 个整数，其中第 i 行第 j 个整数表示初始颜料克数 $c_{i,j}$。

输出描述

对于每组测试数据，若不存在满足两个对称条件的最终分布，则输出一行 -1。 否则输出 n 行，每行包含 m 个非负整数，表示一种合法的最终颜料克数分布 $X$。

样例1

输入

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

输出

0 0 0
0 45 0
0 0 0

说明

初始矩阵总和 $S = 1+2+\dots+9 = 45$。因为 $n=3$ 和 $m=3$ 都是奇数，中心格子 $(2,2)$ 自己构成大小为 1 的对称轨道。可以将所有颜料集中到中心格子，颜料总量不变，并且满足水平和垂直对称条件。因此存在可行方案，输出如上的矩阵。

样例2

输入

1
2 2
4 0
0 0

输出

1 1
1 1

说明

初始矩阵总和 $S = 4$。$n=m=2$ 都是偶数，所有对称轨道的大小均为 4。总和 4 能被 4 整除，因此在四个角各分配 $4 / 4 = 1$ 即可使最终矩阵对称，且总量不变。输出全 1 矩阵为一种可行方案。

样例3

输入

1
3 2
1 1
1 1
1 1

输出

0 0
3 3
0 0

说明

初始矩阵总和 $S = 6$。$n=3$（奇数），$m=2$（偶数），存在大小为 2 的左右对称轨道（例如中间行的第 1 列和第 2 列）。总和 6 是偶数，将 $6 / 2 = 3$ 放在中间行的两个格子上，其他格子置 0，即可满足对称且总量不变。

样例4

输入

1
3 2
1 2
3 4
5 6

输出

-1

说明

初始矩阵总和 $S = 1+2+3+4+5+6 = 21$。$n=3$（奇数），$m=2$（偶数），所有对称轨道的大小为 2 或 4，因此最终总和必须为偶数。这里 $S=21$ 是奇数，不能被 2 整除，故不存在合法方案，输出 -1。