UOJ Logo Universal Online Judge

UOJ

#625. 【统一省选2021 A卷】矩阵游戏

附件下载 统计

Alice 有一个 $n \times m$ 的矩阵 $a_{i,j} (1 \leq i \leq n, 1 \leq j \leq m)$,其每个元素为大小不超过 $10^6$ 的非负整数。

Bob 根据该矩阵生成了一个 $(n - 1) \times (m - 1)$ 的矩阵 $b_{i,j} (1 \leq i \leq n - 1, 1 \leq j \leq m - 1)$,每个元素的生成公式为 $b_{i, j} = a_{i,j} + a_{i,j+1} + a_{i+1,j} + a_{i+1,j+1}$。

现在 Alice 忘记了矩阵 $a_{i,j}$,请你根据 Bob 给出的矩阵 $b_{i,j}$ 还原出 $a_{i,j}$。

输入格式

本题有多组数据。

第一行一个整数 $T$ 表示数据组数。

每组数据第一行两个正整数 $n, m$,表示矩阵 $a_{i,j}$ 的大小。

每组数据第 $2 \sim n$ 行每行 $m − 1$ 个非负整数,表示 $b_{i,j}$。

输出格式

对于每组数据:

  1. 若矩阵 $b_{i,j}$ 无法被生成,则输出一行一个字符串 NO
  2. 若矩阵 $b_{i,j}$ 可被生成,则先输出一行一个字符串 YES,接下来输出 $n$ 行每行 $m$ 个(用单个空格分隔的)大小不超过 $10^6$ 的非负整数表示 $a_{i,j}$。

若有多个矩阵 $a_{i,j}$ 可生成给出的 $b_{i,j}$,输出其中任意一个即可。

样例一

input

3
3 3
28 25
24 25
3 3
15 14
14 12
3 3
0 3000005
0 0

output

YES
7 8 8
8 5 4
4 7 9
YES
4 2 2
5 4 6
5 0 2
NO

限制与约定

对于所有测试数据:$1 \leq T \leq 10, 2 \leq n, m \leq 300, 0 \leq b_{i, j} \leq 4 \times 10^6$。

每个测试点的具体限制见下表:

测试点编号 $n,m \leq$ 特殊限制
$1 \sim 4$ $3$
$5 \sim 7$ $10$ $m = 2$
$8 \sim 10$ $100$
$11 \sim 15$ $300$ $0 \leq b_{i, j} \leq 1$
$16 \sim 20$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载