Xiao Z has recently become interested in studying matrices. He first writes down an $N \times M$ matrix, filling each cell with a non-negative integer less than $P$, and then calculates the sum of the elements for every $2 \times 2$ submatrix. For example, with $N=3, M=3, P=3$, the matrix Xiao Z writes down is:

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

There are $4$ such $2 \times 2$ submatrices. It is easy to calculate the sum of the elements in each, represented as:

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

The $0$s in the first row and first column are added for formatting purposes. Now, Xiao Z wants to see if it is possible to deduce the original matrix from these sums. Since Xiao Z is not very good at mathematics, he has handed this task to you. Of course, Xiao Z has already discovered that the solution is likely not unique; for example, the matrix $B$ below yields the same submatrix sums as matrix $A$:

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

Therefore, if there are multiple matrices that satisfy the requirements, please output the one that is lexicographically smallest. The definition of lexicographical order is as follows: for two matrices $X$ and $Y$, find the cell with the smallest row index where $X$ and $Y$ differ; if there are multiple such cells, choose the one with the smallest column index. The matrix with the smaller value in that cell is lexicographically smaller. For example, comparing matrices $A$ and $B$ above, the first differing cell is at row 1, column 2. Since $A[1][2] < B[1][2]$, matrix $A$ is lexicographically smaller than matrix $B$.

Additionally, Xiao Z's math skills are not so poor that he would make mistakes in addition, so it is guaranteed that the input data always has a solution.

Input

The first line contains three space-separated positive integers $N, M, P$, representing the number of rows, the number of columns, and the upper bound for the elements of the output matrix (i.e., the elements must be less than $P$). The following $N$ lines each contain $M$ space-separated non-negative integers, where the $j$-th number in the $(i+1)$-th line represents the sum of the $2 \times 2$ submatrix with its bottom-right corner at $(i, j)$. The input data guarantees that the first column of the second row and all subsequent rows are $0$, and that the numbers in the rows after the second row do not exceed $4(P-1)$.

$30\%$ of the data satisfies $N, M \le 10$. Another $30\%$ of the data satisfies $P=2$. $100\%$ of the data satisfies $1 < N, M \le 200,\ 1 < P \le 10$.

Output

Output $N$ lines, each containing $M$ space-separated integers (no trailing spaces at the end of lines). The numbers in the $i$-th line of the output should be the elements of the $i$-th row of the matrix you found.

Examples

Input 1

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

Output 1

0 0 2
2 2 1
1 0 0