Problem6165--NOI2010湖北省选 二试 第4题 矩阵

6165: NOI2010湖北省选 二试 第4题 矩阵

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MB

Submit

Description

小Z近日热衷于研究矩阵。他首先写下一个N*M的矩阵,在每个格子里填入一个小于P的非负整数,然后对其中的每个2*2的子矩阵,算出其中各数之和。例如N=3,M=3,P=3,小Z写下的矩阵如下:

其中共有4个2*2的子矩阵,容易算出其中各数之和,表示如下:

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


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

字典序的定义如下:对两个矩阵X和Y,找到X和Y中的数不同的位置中行数最小的那个格子,若有多个这样的格子则取列数最小的那个格子,该格子中的数较小的矩阵字典序也较小。

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

另外,小Z的数学尚未差到连加法都做错的地步,因此保证输入数据都是有解的。

Input

第一行是用空格隔开的三个正整数N,M,P,分别表示矩阵的行数、列数以及输出矩阵元素的上界(即要求输出矩阵元素小于P)。接下来有N行,每行是用空格隔开的M个非负整数,其中第i+1行第j个数表示以格子(i,j)为右下角的2*2子矩阵中各数之和。输入的数据保证第2行及除第1行外的各行的第1个数均为0,且第2行后各行中的数均不超过4(P-1)。输入的数据保证30%的数据满足N,M≤10。另外30%的数据满足P=2。100%的数据满足1<N,M≤200,1<P≤10。

Output

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

Sample Input Copy

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

Sample Output Copy

0 0 2
2 2 1
1 0 0

Source/Category