#P18368. Housing Estate

Housing Estate

Housing Estate

题目描述

ByteBud 公司计划建设一个住宅小区。公司已经购入一块矩形土地,并将它划分成 nn 行、mm 列,共 n⋅mn\cdot m 个矩形格子。用 (i,j)(i,j) 表示第 ii 行、第 jj 列的格子。

公司可以选择一些格子,在每个选中的格子上建造一栋住宅楼,也可以一栋都不建或在所有格子上建楼。你需要决定每个格子上的楼高,楼高用非负整数层数表示,0 表示不建楼。

规划规定,格子 (i,j)(i,j) 上的楼高不能超过 hi,jh_{i,j}。特别地,若 hi,j=0h_{i,j}=0,该格子不能建楼。

此外,公司已经确定了每个四格交点周围的总楼高。对于所有 1≤i<n1\le i<n、1≤j<m1\le j<m,给定整数 si,js_{i,j},要求格子 (i,j)(i,j)、(i+1,j)(i+1,j)、(i,j+1)(i,j+1)、(i+1,j+1)(i+1,j+1) 上的楼高之和恰好等于 si,js_{i,j}。

请判断是否存在满足全部要求的方案;如果存在,输出任意一种方案。

输入格式

第一行两个整数 n,mn,m,表示行数和列数。

接下来 nn 行,每行 mm 个整数,第 ii 行第 jj 个数为 hi,jh_{i,j}。

接下来 n−1n-1 行,每行 m−1m-1 个整数,第 ii 行第 jj 个数为 si,js_{i,j}。

输出格式

如果不存在方案,只输出一行 NIE。

如果存在方案,第一行输出 TAK,接下来输出 nn 行,每行 mm 个非负整数 xi,jx_{i,j},表示各格子上的楼高。它们必须满足

0≤xi,j≤hi,j,0\le x_{i,j}\le h_{i,j},

以及对所有 1≤i<n1\le i<n、1≤j<m1\le j<m,

xi,j+xi+1,j+xi,j+1+xi+1,j+1=si,j.x_{i,j}+x_{i+1,j}+x_{i,j+1}+x_{i+1,j+1}=s_{i,j}.

TAK 和 NIE 中的每个字母都可以使用大写或小写。如果有多种方案,可以输出任意一种。

数据范围

  • 2≤n,m≤3002\le n,m\le300。
  • 0≤hi,j≤10100\le h_{i,j}\le10^{10}。
  • 0≤si,j≤10100\le s_{i,j}\le10^{10}。
  • 每个输入文件只有一组数据。

样例输入 1

3 4
5 7 9 4
3 4 9 6
9 0 8 5
11 26 20
13 16 18

样例输出 1

TAK
0 6 9 3
1 4 7 1
8 0 5 5

样例输入 2

2 2
0 0
0 0
1000

样例输出 2

NIE

样例说明

第一组样例给出一种合法楼高方案。第二组样例的四个格子都不能建楼,楼高总和只能为 0,不能达到要求的 1000,因此无解。