题目描述

$JOIOI$ 王国是一个 $H$ 行 $W$ 列的长方形网格，每个 $1 \times 1$ 的子网格都是一个正方形的小区块。为了提高管理效率，我们决定把整个国家划分成两个省 $JOI$ 和 $IOI$ 。

我们定义，两个同省的区块互相连接，意为从一个区块出发，不用穿过任何一个不同省的区块，就可以移动到另一个区块。有公共边的区块间可以任意移动。

我们不希望划分得过于复杂，因此划分方案需满足以下条件：

• 区块不能被分割为两半，一半属 $JOI$ 省，一半属 $IOI$ 省。

• 每个省必须包含至少一个区块，每个区块也必须属于且只属于其中一个省。

• 同省的任意两个小区块互相连接。

• 对于每一行/列，如果我们将这一行/列单独取出，这一行/列里同省的任意两个区块互相连接。这一行/列内的所有区块可以全部属于一个省。

现给出所有区块的海拔，第 $i$ 行第 $j$ 列的区块的海拔为 $A_{i,j}$ 。设 $JOI$ 省内各区块海拔的极差（最大值减去最小值）为 $R_{JOI}$ ， $IOI$ 省内各区块海拔的极差为 $R_{IOI}$ 。在划分后，省内的交流有望更加活跃。但如果两个区块的海拔差太大，两地间的交通会很不方便。 因此，理想的划分方案是 $max(R_{JOI},R_{IOI})$ 尽可能小。

你的任务是求出 $max(R_{JOI},R_{IOI})$ 至少为多大。

输入格式

第一行，两个整数 $H,W$ ，用空格分隔。

在接下来的 $H$ 行中，第 $i$ 行有 $W$ 个整数 $A_{i,1},A_{i,2}, \cdots ,A_{i,W}$ ，用空格分隔。

输入的所有数的含义见题目描述。

输出格式

一行，一个整数，表示 $max(R_{JOI},R_{IOI})$ 可能的最小值。

数据范围

对于 $15\%$ 的数据， $H,W \leqslant 10$ 。

对于另外 $45\%$ 的数据， $H,W \leqslant 200$ 。

对于所有数据， $2 \leqslant H,W \leqslant 2000,A_{i,j} \leqslant 10^9$ （ $1 \leqslant i \leqslant H,1 \leqslant j \leqslant W$ ）。