Minimizing the Maximum Range in a Valid Two‐Region Partition

You are given an $n\times m$ matrix, where each cell contains an integer magic value. In order to adjust the state of the sacred sword, you must split all the $n\times m$ charms (cells) into two parts, denoted as regions A and B, satisfying the following conditions:

• Every cell belongs to exactly one of the two parts.
• Within each region the cells are 4-directionally connected (neighbors by up, down, left, right) and, moreover, for any two cells in the same region there exists a path (using only cells within the region) that changes direction at most once. In other words, for any two cells $(i,j)$ and $(k,\ell)$ in the same region, either they lie in the same row, or the same column, or one of the two "corner" cells, namely $(i,\ell)$ or $(k,j)$, is also in that region.

For a region, its range is defined as the difference between the maximum and minimum magic values in that region. Your task is to find, among all valid partitions, the minimum possible value of the larger one between the ranges of region A and region B. That is, if a partition results in range difference $R_A$ for region A and $R_B$ for region B, you want to minimize

$$\max\{R_A,\;R_B\} = \max\{(\max A-\min A),\;(\max B-\min B)\}. $$

---

Valid Partition Structures

It turns out that the restrictions force the two regions to have a special "L-convex" structure. In particular, the following types of partitions are valid:

1. Horizontal cut: Choose an integer i ($1 \le i < n$) and let region A be all cells in rows $1,\dots,i$ and region B be the remaining rows.
2. Vertical cut: Choose an integer j ($1 \le j < m$) and let region A be all cells in columns $1,\dots,j$ and region B be the remaining columns.
3. L-shaped partitions: For some choices of $R$ and $C$ ($1 \le R < n$, $1 \le C < m$) you may choose one of the following patterns for region A (with region B being its complement):
   • Top‐Left (TL): All cells in rows $1$ to $R$ together with all cells in rows $R+1$ to $n$ that are in columns $1$ to $C$.
   • Top‐Right (TR): All cells in rows $1$ to $R$ together with all cells in rows $R+1$ to $n$ that are in columns $C+1$ to $m$.
   • Bottom‐Left (BL): All cells in rows $R+1$ to $n$ together with all cells in rows $1$ to $R$ that are in columns $1$ to $C$.
   • Bottom‐Right (BR): All cells in rows $R+1$ to $n$ together with all cells in rows $1$ to $R$ that are in columns $C+1$ to $m$.

You are allowed to choose any valid partition (from the ones listed above) and the answer is the minimum possible value of \(\max\{R_A, R_B\}\) over all such partitions. Note that in each case, the cells in both regions always form connected sets that satisfy the one‐turn condition.

---

Input Description

The first line contains two integers n and m ($n, m \ge 2$), indicating the number of rows and columns of the matrix.

Then follow n lines, each containing m integers. The j-th integer in the i-th line represents the magic value in that cell.

---

Output Description

Output one integer: the minimum possible value of \(\max\{R_A, R_B\}\) among all valid partitions.

inputFormat

The input begins with two integers n and m (with n, m \ge 2), followed by n lines each containing m integers, representing the matrix.

outputFormat

Output a single integer --- the minimum possible maximum range among the two regions.

sample

2 2
1 2
3 4

1