The Kingdom of Bobland is a rectangular grid of ~H \times W~ cells. In the Kingdom of Bobland, in order to improve efficiency of administrative institutions, the country will be divided into two regions called DMOJ and PEG.

Since we do not want to divide it in a complicated way, the division must satisfy the following conditions:

• Each region must contain at least one cell.
• Each cell must belong to exactly one of two regions.
• For every pair of cells in the DMOJ region, we can travel from one to the other by passing through cells belonging to the DMOJ region only. When move from a cell to another cell, the two cells must share an edge. The same is true for the PEG region.
• For each row or column, if we take all the cells in that row or column, the cells belonging to each region must be connected. All the cells in a row or column may belong to the same region.

Each cell has an integer called the altitude. After we divide the country into two regions, it is expected that traveling in each region will be active. But, if the difference of the altitudes of cells are large, traveling between them becomes hard. Therefore, Bob would like to minimize the maximum of the difference of the altitudes between cells belonging to the same region. In other words, Bob would like to minimize the larger value of

• the difference between the maximum and the minimum altitudes in the DMOJ region, and
• the difference between the maximum and the minimum altitudes in the PEG region.

Given the altitudes of cells in the Kingdom of Bobland, can you write a program which calculates the minimum of the larger value of the difference?

Input Specification:

The first line of input contains two integers ~H~, ~W~, (~2 \le H, W \le 2\,000~) which means the size of Kingdom of Bobland.

Each of the following ~H~ lines contains ~W~ integers ~a_{i,j}~, (~1 \le i \le H~, ~1 \le j \le W~, ~1 \le a_{i,j} \le 10^9~), indicating that the cell in the ~i~-th row and ~j~-th column has altitude ~a_{i,j}~.

Output Specification:

Output one integer, the minimum of the larger value of the difference.

Constraints

Subtask	Points	Additional constraints
~1~	~15~	~H, W \le 10~
~2~	~45~	~H, W \le 200~
~3~	~40~	No additional constraints.

Sample Input 1

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

Sample Output 1

11

Explanation for Sample Case 1

One possible way to divide the given grid is shown as follows, where the max difference for both DMOJ and PEG are ~11~.

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

Sample Input 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

Sample Output 2

18