Matrix Reconstruction from 2x2 Submatrix Sums

You are given three integers N, M and P, where N and M denote the dimensions of a matrix A and P is a positive integer. The matrix A has N rows and M columns. Each element of A is a nonnegative integer less than P.

For every 2x2 submatrix of A (that is, for every i from 1 to N-1 and every j from 1 to M-1), you are given the sum:

$$A_{i,j} + A_{i,j+1} + A_{i+1,j} + A_{i+1,j+1} = S_{i,j} $$

Your task is to reconstruct A from the given sums. It is guaranteed that there is at least one solution. If multiple matrices satisfy the condition, output the one that is lexicographically smallest.

The lexicographical order is defined as follows: Given two matrices X and Y, find the first position (in row-major order) where they differ. The matrix with the smaller element at that position is considered lexicographically smaller.

Note: Although the 2x2 submatrix sums are uniquely provided for submatrices defined by rows 1 through N-1 and columns 1 through M-1, you should assume that these sums are computed using the following formula:

$$A_{i,j} + A_{i,j+1} + A_{i+1,j} + A_{i+1,j+1} = S_{i,j}\quad (1 \le i \le N-1,\; 1 \le j \le M-1) $$

Your answer matrix A (of size N x M) should satisfy 0 ≤ A_i,j < P for all valid i and j.

inputFormat

The first line of input contains three integers N, M and P.

The following N-1 lines each contain M-1 integers. The j-th integer in the i-th of these lines is S_i,j, the sum of the 2x2 submatrix with top‐left corner at row i and column j.

Note: It is guaranteed that the input data has at least one solution.

outputFormat

Output the reconstructed matrix A with N rows. Each row contains M integers separated by spaces. The matrix must be the lexicographically smallest solution.

sample

3 3 3
4 5
5 3

0 1 2
1 2 0
2 0 1

</p>