Matrix Problem

Problem Description

There is an $n\times m$ matrix; you need to fill in a number $x_{i,j}$ at each position $(i, j)$.

There are several constraints. For each position $(i, j)$, it must satisfy $l_{i,j}\leq x_{i,j}\leq r_{i,j}$.

Further, for all $i, j(1\leq i\leq n, 1\leq j\leq m-1)$, it must satisfy $x_{i,j} + x_{i, j+1} \leq a_{i,j}$. For all $i, j(1\leq i\leq n-1, 1\leq j\leq m)$, it must satisfy $x_{i,j} + x_{i + 1, j} \geq b_{i,j}$.

Input Format

The first line contains two integers $n, m(2\leq n, m\leq 50)$.

The next $n$ lines each contain $m$ numbers $l_{i,j} (1\leq l_{i, j}\leq 10^9)$.

The next $n$ lines each contain $m$ numbers $r_{i,j} (1\leq r_{i, j}\leq 10^9)$.

The next $n$ lines each contain $m-1$ numbers $a_{i,j} (0\leq a_{i, j}\leq 2\times 10^9)$.

The next $n-1$ lines each contain $m$ numbers $b_{i,j} (0\leq b_{i, j}\leq 2\times 10^9)$.

The input guarantees that a solution always exists.

Output Format

Output $n$ lines of $m$ numbers each, representing one valid solution. Any valid solution is accepted.

Sample Input

2 2
0 1
2 3
2 3
4 5
4
8
4 5

Sample Output

1 2
3 4

Constraints

$2\leq n, m\leq 50$; all bounds are within the ranges given in the input; a solution always exists.

Hint

• Every constraint is of the form "$x_u - x_v \leq c$" or "$x_u - x_v \geq c$", which is a classic system of difference constraints. Build a graph and run the Bellman-Ford / SPFA shortest-path algorithm to find one feasible assignment.