#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/**
* JOI 2016/2017 Final Round - Kingdom of JOIOI
* Zaman Karmaşıklığı: O(H * W * log(max_A))
*/
int H, W;
int A[2005][2005];
int global_min = 2e9, global_max = -2e9;
// X farkı için geçerli bir bölme olup olmadığını kontrol eder
bool check(int X) {
// JOI bölgesinin [global_min, global_min + X] aralığında olması gerektiğini varsayalım
// Bu bölgeyi merdiven şeklinde (sol üstten genişleyerek) oluşturmaya çalışalım
vector<int> border(H);
int current_max_col = W;
for (int i = 0; i < H; i++) {
int row_limit = 0;
for (int j = 0; j < W; j++) {
// Eğer hücre JOI kriterine uyuyorsa bölgeyi genişlet
if (A[i][j] <= global_min + X) {
row_limit = j + 1;
} else {
break;
}
}
// Sınır monoton olmalı (merdiven basamakları sola gidemez)
current_max_col = min(current_max_col, row_limit);
border[i] = current_max_col;
}
// IOI bölgesinde kalan hücrelerin [global_max - X, global_max] aralığında olup olmadığını kontrol et
for (int i = 0; i < H; i++) {
for (int j = border[i]; j < W; j++) {
if (A[i][j] < global_max - X) return false;
}
}
return true;
}
// Matrisi dikey/yatay çevirerek 4 simetriyi simüle eder
void flip_v() {
for (int i = 0; i < H / 2; i++) {
for (int j = 0; j < W; j++) swap(A[i][j], A[H - 1 - i][j]);
}
}
void flip_h() {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W / 2; j++) swap(A[i][j], A[i][W - 1 - j]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> H >> W;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> A[i][j];
global_min = min(global_min, A[i][j]);
global_max = max(global_max, A[i][j]);
}
}
int low = 0, high = global_max - global_min;
int ans = high;
while (low <= high) {
int mid = low + (high - low) / 2;
bool possible = false;
// 4 farklı köşe başlangıcı için kontrol et
for (int f = 0; f < 4; f++) {
if (f == 1) flip_v();
if (f == 2) flip_h();
if (f == 3) flip_v();
if (check(mid)) {
possible = true;
break;
}
}
// Matrisi orijinal haline getir (isteğe bağlı, sonraki low/high için temizlik)
flip_h();
if (possible) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << ans << endl;
return 0;
}
