The Kingdom of JOIOI

The Kingdom of JOIOI is a rectangular grid of $H \times W$ cells. To make its administrative institutions more efficient, the kingdom will divide the country into two regions called "JOI" and "IOI".

The kingdom does not want a complicated division, so the division must satisfy all of the following conditions:

• Each region contains at least one cell.
• Each cell belongs to exactly one of the two regions.
• For every pair of cells in the JOI region, you can travel from one to the other by passing only through cells of the JOI region. Each move goes between two cells that share an edge. The same holds for the IOI region.
• In every row and every column, the cells of that row or column that belong to each region are contiguous. All the cells of a row or column may belong to the same region.

Each cell has an integer called its altitude. After the division, the kingdom expects travel within each region to become active. However, traveling between cells with a large altitude difference is hard. Therefore, the kingdom wants to minimize the maximum altitude difference between cells of the same region. In other words, it wants to minimize the larger of these two values:

• the difference between the maximum and the minimum altitude in the JOI region, and
• the difference between the maximum and the minimum altitude in the IOI region.

Given the altitudes of the cells of the Kingdom of JOIOI, write a program that computes the minimum possible value of the larger of these two differences over all valid divisions.

The first line contains two integers $H$ and $W$ separated by a space. The Kingdom of JOIOI is a grid of $H \times W$ cells.

The $i$-th of the following $H$ lines ($1 \le i \le H$) contains $W$ integers $A_{i,1}, A_{i,2}, \ldots, A_{i,W}$ separated by spaces. The cell in the $i$-th row from the top and the $j$-th column from the left ($1 \le j \le W$) has altitude $A_{i,j}$.

Print one line: the minimum, over all valid divisions, of the larger of the altitude difference (maximum minus minimum) in the JOI region and the altitude difference in the IOI region.

• $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$)