JOIOI Kingdom Partition

The JOIOI Kingdom is represented by a grid of size $H \times W$, where each cell (a 1×1 square) has an altitude $A_{i,j}$. You are to partition the grid into two provinces, JOI and IOI, satisfying the following conditions:

• Each cell is assigned to exactly one province and neither province is empty.
• In the whole grid, the cells of the same province are connected (adjacent by common side).
• In every row and every column (when considered separately), the cells belonging to the same province are contiguous (i.e. any two cells in that row/column that belong to the same province can be reached by moving through adjacent cells in that row/column without leaving that province).

Let the altitude range in province JOI be $$ R_{JOI} = \max(\{A_{i,j}\ \text{in JOI}\}) - \min(\{A_{i,j}\ \text{in JOI}\}) $$ and similarly for province IOI, denote $$ R_{IOI} = \max(\{A_{i,j}\ \text{in IOI}\}) - \min(\{A_{i,j}\ \text{in IOI}\}). $$ The objective is to achieve a partition so that the quantity $$ \max(R_{JOI},\,R_{IOI}) $$ is as small as possible. Output the minimum possible value of this quantity over all valid partitions.

Note: Under the connectivity constraints on each row and column, the partition can be described by a sequence of integers $k_1, k_2, \dots, k_H$ with $0 \le k_i \le W$ for each row $i$, such that in row $i$, the left $k_i$ cells (columns $1$ through $k_i$) are assigned to one province (say, JOI) and the remaining cells are assigned to the other province (IOI). In order to guarantee connectivity among the cells assigned in different rows, the sequence must be monotone non-decreasing (i.e. $k_1 \le k_2 \le \cdots \le k_H$).

inputFormat

The first line contains two integers $H$ and $W$, denoting the number of rows and columns respectively.

Then follow $H$ lines, each containing $W$ integers. The $j$-th integer in the $i$-th line is $A_{i,j}$, the altitude of the corresponding cell.

outputFormat

Output a single integer representing the minimum possible value of $\max(R_{JOI}, R_{IOI})$ achievable by a valid partition of the grid.

sample

2 2
1 100
100 1

99