Description

Xiao Z has recently been studying matrices. He first wrote an $N\times M$ matrix where each cell contains a non-negative integer less than $P$. Then, for every $2\times 2$ submatrix, he computed the sum of its four numbers.

For example, when $N=3, M=3, P=3$, the matrix he wrote is:

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

There are $4$ submatrices of size $2\times 2$, and their sums are:

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

(The zeros in the first row and first column are added only for formatting.)

Now Xiao Z wants to see whether he can reconstruct the original matrix from these sums. Since his math is not very good, he asks you to do it.

Of course, the solution may not be unique. For example, the following matrix produces the same sums as above:

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

If multiple matrices satisfy the requirement, output the lexicographically smallest one.

Lexicographic order is defined as follows: for two solution matrices $X$ and $Y$, find the cell with the smallest row index where they differ; if there are multiple such cells, take the one with the smallest column index. The matrix with the smaller value at that cell is lexicographically smaller.

For the two example matrices above, the first differing cell is the second cell in the first row, and since the first matrix has a smaller value there, it is lexicographically smaller.

Also, it is guaranteed that the input is solvable.

Input Format

The first line contains three positive integers $N, M, P$, denoting the number of rows and columns of the matrix and the value range of each number. Then follow $N$ lines, each containing $M$ non-negative integers. In the $i$-th line, the $j$-th number is the sum of the $2 \times 2$ submatrix whose bottom-right corner is cell $(i, j)$. The numbers in the first row and the first column are guaranteed to be $0$, and each sum does not exceed $4 (P-1)$.

Output Format

Output $N$ lines, each containing $M$ integers describing the matrix you reconstructed, with adjacent integers separated by single spaces. Do not print trailing spaces at the end of a line.

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

0 0 2
2 2 1
1 0 0

Hint

$1 \le N, M \le 200$.

$2 \le P \le 10$.

Thanks to @ASC_8384 for providing the problem statement.

Translated by ChatGPT 5