Problem Description

Input Format

Read the following input from standard input:

• The first line contains two integers $H$ and $W$ separated by a space. These represent that the Kingdom of JOIOI is divided into a grid of $H$ rows and $W$ columns.
• The following $H$ lines contain $W$ integers each, separated by spaces. The $i$-th line ($1 \leq i \leq H$) contains the integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, W}$, which represent the elevation of the cell in the $i$-th row and $j$-th column ($1 \leq j \leq W$) of the Kingdom of JOIOI.

Output Format

Output to standard output the minimum value of the larger difference between the maximum and minimum elevations within the regions JOI and IOI when the kingdom is divided into two regions satisfying the given conditions.

Sample Input and Output

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

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

Notes/Hints

Task

Given the elevation of each cell in the Kingdom of JOIOI, write a program to find the minimum value of the larger difference between the maximum and minimum elevations within the regions JOI and IOI when the kingdom is divided into two regions satisfying the given conditions.

Constraints

All input data satisfies the following conditions:

• $2 \leq H \leq 2,000$.
• $2 \leq W \leq 2,000$.
• $1 \leq A_{i, j} \leq 1,000,000,000$ ($1 \leq i \leq H$, $1 \leq j \leq W$).

Subtask 1 [15 points]

Satisfies the following conditions:

• $H \leq 10$.
• $W \leq 10$.

Subtask 2 [45 points]

Satisfies the following conditions:

• $H \leq 200$.
• $W \leq 200$.

Subtask 3 [40 points]

No additional constraints.

Sample Explanation 1

In this input example, the regions can be divided as shown in the figure below, where J represents the region JOI and I represents the region IOI.

J J J I
J J J I
J J I I
J I I I

For example, the following division does not satisfy the conditions because the region IOI is not contiguous in the 3rd column from the left.

J J I I
J J J I
J J J I
J I I I

见题面 Input 部分

见题面 Output 部分