JOIOI 王国

JOIOI 王国是一个被$H$行$W$列方格划分而成的长方形。为了提高行政效率，JOIOI 王国决定将整个国家分为两个地区 JOI 和 IOI。

为了防止分割变得过于复杂，我们决定按照以下条件进行划分:

• 每个地区至少包含一个方格。
• 每个方格属于且只属于两个地区中的一个。
• 属于地区 JOI 的两个方格之间，可以通过在不进入其他地区的方格上重复移动来进行移动。对于地区 IOI 也同样适用。
• 对于每一行和每一列，当将该行或该列的所有方格取出后，每个地区的方格都是连续的。但是，同一行或同一列的所有方格都属于同一个地区也是允许的。

每个方格都有一个称为 "標高" 的整数。我们预期，在进行地区内的移动时活动会频繁起来。如果地区内的標高差异过大，移动将变得困难。因此，我们希望在同一个地区内尽量减小標高差。换句话说，我们希望最小化地区 JOI 中的標高最大值与最小值之间的差和地区 IOI 中的標高最大值与最小值之间的差中的较大值。

任务

给定JOIOI王国每个方格的標高，编写一个程序，找到满足条件的地区划分，并输出地区 JOI 中的標高最大值与最小值之间的差和地区 IOI 中的標高最大值与最小值之间的差中的较大值的最小值。

输入

从标准输入读取以下信息：

• 第一行包含两个整数 $H, W$，以空格分隔。它们表示JOIOI王国由$H$行$W$列方格组成。
• 接下来的$H$行中的第$i$行($1 \leqq i \leqq H$)包含$W$个整数 $A_{i, 1}, A_{i, 2}, \ldots, A_{i, W}$，以空格分隔。这表示JOIOI王国中第$i$行、第$j$列($1 \leqq j \leqq W$)的標高为$A_{i, j}$。

输出

将结果输出到标准输出，输出满足条件的地区划分后，地区 JOI 中的標高最大值与最小值之间的差和地区 IOI 中的標高最大值与最小值之间的差中的较大值的最小值。

限制

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

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

输入示例 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

但是，例如下面的划分是不符合条件的，因为在第3列中，IOI地区不是连续的。

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