P7515 [NOI Qualifier Joint Contest 2021 Paper A] Matrix Game

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.

**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}$.

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.

**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$ | $m = 2$ | | $11 \sim 15$ | $300$ | $0 \le b_{i, j} \le 1$ | | $16 \sim 20$ | $300$ | None | Translated by ChatGPT 5