题目描述

小 Z 近日闲来无事，便研究起矩阵来。他先写了一个 $N\times M$ 的矩阵，每个格子里填入了一个小于 $P$ 的非负整数，然后他对于每个 $2\times 2$ 的子矩阵，算出了其中数的和。

譬如 $N=3, M=3, P=3$，小 Z 写的矩阵如下：

$$A = \begin{pmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{pmatrix} $$

共有 $4$ 个 $2\times 2$ 的子矩阵，容易算出它们的和如下：

$$A = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 4 & 5 \\ 0 & 5 & 3 \end{pmatrix} $$

(第一行和第一列的 $0$ 是为了格式美观而添加进去的)

现在小 Z 想试一试能不能根据这些和推算出原矩阵。由于小 Z 的数学并不好，因此这个任务就交给你了。

当然，小 Z 早就发现了，解很可能不唯一，譬如下面的矩阵算出的和与 $A$ 相同：

$$A = \begin{pmatrix} 0 & 2 & 1 \\ 0 & 2 & 0 \\ 2 & 1 & 0 \end{pmatrix} $$

示意图在有多个矩阵满足要求的情况下请你输出字典序最小的那一个。

字典序的比较方式如下：对于两个解矩阵 $X$ 和 $Y$，找到 $X$ 和 $Y$ 不同的位置中行数最小的那一个格子，若有多个则取列数最小的那个格子，该位置较小的矩阵字典序较小。

譬如上述的矩阵 $A$ 和 $B$，第一个不同的格子应是第一行第二个格子，而 $A[1][2] < B[1][2]$，故矩阵 $A$ 的字典序比 $B$ 小。

另外，小 Z 的数学还没有差到加法都做错，因此保证输入数据都是有解的。

输入格式

第一行包含三个正整数 $N, M, P$ 表示矩阵的行数列数以及每个数的范围，接下来 $N$ 行每行包含 $M$ 个非负整数，其中第 $i$ 行第 $j$ 个数表示以格子 $(i,j)$ 为右下角的 $2 \times 2$ 子矩阵中的数的和。保证第一行与第一列的数均为 $0$，且每个和都不超过 $4 (P-1)$。

输出格式

包含 $N$ 行，每行 $M$ 个整数，描述你求出的矩阵，相邻的整数用空格分开。（行末不要有多余空格）

3 3 3
0 0 0
0 4 5
0 5 3

0 0 2
2 2 1
1 0 0

提示

$1 \le N, M \le 200$

$2 \le P \le 10$

感谢 @ASC_8384 提供题面