22373번 - Buttons 스페셜 저지다국어

There is an $H \times W$ grid, with one button in each cell. Initially, all buttons are off. You will push them and turn them on.

Your task is to find a "good" timing of pressing the buttons. Let $t_{ij}$ be the timing to push the button of row $i$ and column $j$. The timing is said to be "good" if and only if the following conditions are satisfied.

• $t_{ij}$ is an integer between $0$ and $10^9$ for all $i$ and $j$.
• $t_{kl} + a_{ij} \le t_{ij} \le t_{kl} + b_{ij}$ for every cell $kl$ which is a horizontal or vertical neighbor of the cell $ij$, i.e., $|i - k| + |j - l| = 1$.

Write a program to output a "good" timing for the given $a$ and $b$. If there are several possible timings, you can output any of them. If there is no "good" timing, you should output $-1$.

The input consists of a single test case of the following format.

$H$ $W$

$a_{11}$ $\dots$ $a_{1W}$

$\vdots$

$a_{H1}$ $\dots$ $a_{HW}$

$b_{11}$ $\dots$ $b_{1W}$

$\vdots$

$b_{H1}$ $\dots$ $b_{HW}$

$H$ and $W$ represent the height and width of the given grid ($w \le H, W \le 50$). $a_{ij}$ and $b_{ij}$ represent the range of time differences for the button of row $i$ and column $j$ ($-100,000 \le a_{ij} \le b_{ij} \le 100,000$).

If there is a "good" timing, output it in the following format.

$T_{11}$ $\dots$ $T_{1W}$

$\vdots$

$T_{H1}$ $\dots$ $T_{HW}$

$T_{ij}$ is an integer representing the timing to push the button of row $i$ and column $j$. The timings should satisfy the conditions defined in the problem statement. If there are multiple correct answers, you can print any of them.

If there is no "good" timing, you should output $-1$ instead.