Description

Alice has an $n \times m$ matrix $a_{i, j}$ ($1 \le i \le n$, $1 \le j \le m$), where each element is a non-negative integer with value at most ${10}^6$.

Bob uses this matrix to generate an $(n - 1) \times (m - 1)$ matrix $b_{i, j}$ ($1 \le i \le n - 1$, $1 \le j \le m - 1$). Each element is generated by

$$b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1}$$

Now Alice has forgotten the matrix $a_{i, j}$. Please restore $a_{i, j}$ from the matrix $b_{i, j}$ given by Bob.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases. For each test case:

The first line contains two positive integers $n, m$, the size of matrix $a_{i, j}$.
The next $n - 1$ lines each contain $m - 1$ non-negative integers, representing $b_{i, j}$.

Output Format

For each test case:

1. If the matrix $b_{i, j}$ cannot be generated, output one line containing the string NO.
2. If the matrix $b_{i, j}$ can be generated, first output one line containing the string YES, then output $n$ lines each containing $m$ non-negative integers (separated by single spaces) with value at most ${10}^6$, representing $a_{i, j}$.

If multiple matrices $a_{i, j}$ can generate the given $b_{i, j}$, output any one of them.

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

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

Hint

Constraints

For all testdata: $1 \le T \le 10$, $2 \le n, m \le 300$, $0 \le b_{i, j} \le 4 \times {10}^6$.

The detailed limits for each test point are shown in the table below:

Test Point ID	$n, m \le$	Special Constraint
$1 \sim 4$	$3$	None
$5 \sim 7$	$10$	$m = 2$
$8 \sim 10$	$100$
$11 \sim 15$	$300$	$0 \le b_{i, j} \le 1$
$16 \sim 20$		None

Translated by ChatGPT 5