矩阵问题

题目描述

有一个$n\times m$的矩阵，你需要在每个位置$(i, j)$填上一个数$x_{i,j}$。

有若干个限制，每个对于每个位置$(i, j)$，满足$l_{i,j}\leq x_{i,j}\leq r_{i,j}$。

其次，对于所有$i, j(1\leq i\leq n, 1\leq j\leq m-1)$，满足$x_{i,j} + x_{i, j+1} \leq a_{i,j}$。对于所有$i, j(1\leq i\leq n-1, 1\leq j\leq m)$，满足$x_{i,j} + x_{i + 1, j} \geq b_{i,j}$。

输入格式

第一行两个整数$n, m(2\leq n, m\leq 50)$。

接下来$n$行，每行$m$个数$l_{i,j} (1\leq l_{i, j}\leq 10^9)$。

接下来$n$行，每行$m$个数$r_{i,j} (1\leq r_{i, j}\leq 10^9)$。

接下来$n$行，每行$m-1$个数$a_{i,j} (0\leq a_{i, j}\leq 2\times 10^9)$。

接下来$n-1$行，每行$m$个数$b_{i,j} (0\leq b_{i, j}\leq 2\times 10^9)$。

数据保证一定有解。

输出格式

输出$n$行$m$列，表示一个解。输出任意解即可。

样例输入

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

样例输出

1 2
3 4