Vương quốc JOIOI là một bảng chữ nhật gồm \(H\times W\) ô. Để nâng cao hiệu quả quản lý, vương quốc sẽ được chia thành hai vùng mang tên JOI và IOI. Cách chia phải thỏa mãn:

• Mỗi vùng chứa ít nhất một ô và mỗi ô thuộc đúng một vùng.
• Giữa hai ô bất kỳ của cùng một vùng, có thể đi qua các ô của vùng đó bằng các bước giữa hai ô chung cạnh.
• Trên mỗi hàng hoặc cột, các ô thuộc mỗi vùng phải liên thông. Một hàng hoặc cột có thể hoàn toàn thuộc một vùng.

Mỗi ô có một độ cao nguyên. Với mỗi vùng, xét hiệu giữa độ cao lớn nhất và nhỏ nhất trong vùng. Hãy chia vương quốc hợp lệ sao cho giá trị lớn hơn trong hai hiệu này là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa \(H,W\).
• \(H\) dòng tiếp theo, dòng thứ \(i\) chứa \(W\) số nguyên \(A_{i,1},A_{i,2},\ldots,A_{i,W}\).

Dữ liệu ra

In giá trị nhỏ nhất có thể của hiệu độ cao lớn nhất trong hai vùng.

Ràng buộc

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

Phân nhóm

1. \(15\) điểm: \(H\le 10\) và \(W\le 10\)
2. \(45\) điểm: \(H\le 200\) và \(W\le 200\)
3. \(40\) điểm: Không có ràng buộc bổ sung

Ví dụ

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

11

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

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

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

18

Nguồn

JOI 2016/2017, Vòng chung kết.