JOIOI 王国是一个 $H \times W$ 的矩形网格。为了提高行政机构的效率，JOIOI 王国将被划分为两个区域，分别称为“JOI”和“IOI”。由于我们不希望以复杂的方式进行划分，因此划分必须满足以下条件：

• 每个区域必须至少包含一个单元格。
• 每个单元格必须恰好属于两个区域中的一个。
• 对于 JOI 区域中的每一对单元格，我们都可以通过仅经过属于 JOI 区域的单元格从一个单元格到达另一个单元格。在从一个单元格移动到另一个单元格时，这两个单元格必须共享一条边。IOI 区域的情况也是如此。
• 对于每一行或每一列，如果我们取该行或该列中的所有单元格，则属于每个区域的单元格必须是连通的。某一行或某一列中的所有单元格可能属于同一个区域。

每个单元格都有一个称为海拔的整数。在我们把国家划分为两个区域后，预期每个区域内的通行将会很频繁。但是，如果单元格之间的海拔差很大，它们之间的通行就会变得困难。因此，我们希望最小化属于同一区域的单元格之间的最大海拔差。换句话说，我们希望最小化以下两个值中的较大者：

• JOI 区域中最大海拔与最小海拔之差，以及
• IOI 区域中最大海拔与最小海拔之差。

题目描述

给定 JOIOI 王国中各单元格的海拔，编写一个程序，计算当我们把国家划分为两个区域时，JOI 区域中最大海拔与最小海拔之差和 IOI 区域中最大海拔与最小海拔之差这两个值中的较大者的最小值。

输入格式

从标准输入读取以下数据。

• 第一行包含两个空格分隔的整数 $H, W$。这意味着 JOIOI 王国是一个 $H \times W$ 的矩形网格。
• 接下来的 $H$ 行中的第 $i$ 行 ($1 \le i \le H$) 包含 $W$ 个空格分隔的整数 $A_{i,1}, A_{i,2}, \dots, A_{i,W}$。这意味着从上往下第 $i$ 行、从左往右第 $j$ 列 ($1 \le j \le W$) 的单元格的海拔为 $A_{i,j}$。

输出格式

输出一行到标准输出。该输出包含当我们把国家划分为两个区域时，JOI 区域中最大海拔与最小海拔之差和 IOI 区域中最大海拔与最小海拔之差这两个值中的较大者的最小值。

数据范围

所有输入数据满足以下条件：

• $2 \le H \le 2\,000$
• $2 \le W \le 2\,000$
• $1 \le A_{i,j} \le 1\,000\,000\,000$ ($1 \le i \le H, 1 \le j \le W$)

子任务

子任务 1 [15 分]

满足以下条件：

• $H \le 10$
• $W \le 10$

子任务 2 [45 分]

满足以下条件：

• $H \le 200$
• $W \le 200$

子任务 3 [40 分]

没有附加限制。

样例

样例输入 1

4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

样例输出 1

11

例如，在此样例输入中，我们将国家划分为两个区域如下。这里，“J”表示 JOI 区域，“I”表示 IOI 区域。

J J J I
J J J I
J J I I
J I I I

以下划分不满足条件，因为在从左往右第三列中，带有“I”的单元格不连通。

J J I I
J J J I
J J J I
J I I I

样例输入 2

8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16

样例输出 2

18