Buttons

시간 제한2초메모리 제한512 MB

요약

각 격자 칸에 0 이상 10^9 이하의 정수 시각을 부여해 모든 인접한 두 칸이 t_kl + a_ij <= t_ij <= t_kl + b_ij를 만족하도록 하거나, 불가능하면 -1을 출력한다.

난이도: 보통10점 중 5점
유형: 최단 경로, 그래프, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1

입력

3 3
-2 1 -2
1 -2 1
-2 1 -2
-1 2 -1
2 -1 2
-1 2 -1

예상 출력

0 1 0
1 0 2
0 2 0

예제 2
입력
```
2 2
1 1
1 1
1 1
1 1
```
예상 출력
```
-1
```