题目描述

小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$ 的子矩阵，容易算出其中各数之和，表示如下：

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

第一行和第一列的 $0$ 是为了格式美观而添加进去的。现在小Z想试一试能不能根据这些和推算出原矩阵。因为小Z的数学没学好，所以这个任务就交给你了。当然，小Z早就发现：解很可能不唯一，例如对下面的矩阵 $B$ 算出的其中各数之和与矩阵 $A$ 相同。

$$ B= \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$，分别表示矩阵的行数、列数以及输出矩阵元素的上界（即要求输出矩阵元素小于 $P$）。接下来有 $N$ 行，每行是用空格隔开的 $M$ 个非负整数，其中第 $i+1$ 行第 $j$ 个数表示以格子 $(i,j)$ 为右下角的 $2 \times 2$ 子矩阵中各数之和。输入的数据保证第 $2$ 行及除第 $1$ 行外的各行的第 $1$ 个数均为 $0$，且第 $2$ 行后各行中的数均不超过 $4(P-1)$。

输入的数据保证 $30%$ 的数据满足 $N, M \le 10$。另外 $30%$ 的数据满足 $P=2$。$100%$ 的数据满足 $1 < N, M \le 200,\ 1 < P \le 10$。

输出格式

输出包含 $N$ 行，每行是用空格隔开的 $M$ 个整数（行末不允许多余的空格），第 $i$ 行输出中的数就是你求出的矩阵的第 $i$ 行中的数。

样例数据

输入（input.txt）

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

输出（output.txt）

0 0 2
2 2 1
1 0 0