JOIOI 왕국

JOIOI 왕국은 $H \times W$ 크기의 직사각형 격자 모양이다. 행정 기관의 효율을 높이려고 JOIOI 왕국은 나라를 "JOI" 지역과 "IOI" 지역, 두 지역으로 나누기로 했다.

복잡하게 나누고 싶지는 않으므로 분할은 다음 조건을 모두 만족해야 한다.

• 각 지역에는 칸이 하나 이상 있어야 한다.
• 모든 칸은 두 지역 중 정확히 한 지역에 속해야 한다.
• JOI 지역에 속한 임의의 두 칸 사이는 JOI 지역의 칸만 지나서 오갈 수 있어야 한다. 한 칸에서 다른 칸으로 이동할 때 두 칸은 변을 공유해야 한다. IOI 지역도 마찬가지다.
• 어느 행이나 열을 보더라도, 그 행이나 열에서 각 지역에 속한 칸들은 연속해야 한다. 한 행이나 열의 모든 칸이 같은 지역에 속해도 된다.

각 칸에는 고도라는 정수가 하나씩 있다. 나라를 두 지역으로 나눈 뒤에는 지역 안에서 여행이 활발해지기를 기대한다. 그런데 칸끼리 고도 차이가 크면 그 사이를 여행하기가 어렵다. 그래서 같은 지역에 속한 칸들의 고도 차이의 최댓값을 최소로 만들려고 한다. 다시 말해 다음 두 값 중 큰 값을 최소화하려고 한다.

• JOI 지역에서 고도의 최댓값과 최솟값의 차
• IOI 지역에서 고도의 최댓값과 최솟값의 차

JOIOI 왕국 각 칸의 고도가 주어질 때, 나라를 두 지역으로 나누었을 때 위 두 값 중 큰 값의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 두 정수 $H$와 $W$가 공백으로 구분되어 주어진다. JOIOI 왕국이 $H \times W$ 크기의 격자라는 뜻이다.

이어지는 $H$개의 줄 중 $i$번째 줄($1 \le i \le H$)에는 $W$개의 정수 $A_{i,1}, A_{i,2}, \ldots, A_{i,W}$가 공백으로 구분되어 주어진다. 위에서 $i$번째 행, 왼쪽에서 $j$번째 열($1 \le j \le W$)에 있는 칸의 고도가 $A_{i,j}$라는 뜻이다.

나라를 두 지역으로 나누었을 때, JOI 지역의 고도 최댓값과 최솟값의 차와 IOI 지역의 고도 최댓값과 최솟값의 차 중 큰 값의 최솟값을 한 줄에 출력한다.

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