#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 3007;
int kt[MAXN][MAXN];
int T[MAXN][MAXN];
int n, m;
int kolumna[MAXN][2][2];
pair<int, int> przedzial[MAXN];
struct trojka {
int x, y;
int a;
};
vector<trojka> v;
bool spr(int d) {
// cout << "d = " << d << '\n';
rep(i, n) {
rep(c, 2) {
kolumna[i][c][0] = -1;
kolumna[i][c][1] = MAXN + 1;
}
rep(j, m) {
kt[i][j] = 0;
}
}
int sz = v.size();
trojka tmin = v[0];
trojka tmax = v[sz - 1];
// cout << tmin.a << " " << tmax.a << '\n';
int it = 0;
while (it < sz && (v[it].a < (tmax.a - d))) {
// cout << "v = " << v[it].a << '\n';
kt[v[it].x][v[it].y] = 1;
kolumna[v[it].x][0][0] = max(kolumna[v[it].x][0][0], v[it].y);
kolumna[v[it].x][0][1] = min(kolumna[v[it].x][0][1], v[it].y);
it++;
}
it = sz - 1;
while (it >= 0 && (v[it].a > (tmin.a + d))) {
if (kt[v[it].x][v[it].y] == 1) {
return false;
}
kt[v[it].x][v[it].y] = 2;
kolumna[v[it].x][1][0] = max(kolumna[v[it].x][1][0], v[it].y);
kolumna[v[it].x][1][1] = min(kolumna[v[it].x][1][1], v[it].y);
it--;
}
// cout << "d = " << d << '\n';
bool czy = false;
bool czy1 = true;
int wys = 0;
int wys2 = MAXN;
// rep(i, n) {
// rep(c, 2) {
// cout << kolumna[i][c][0] << " " << kolumna[i][c][1] << '\n';
// }
// cout << '\n';
// }
rep(i, n) {
if (kolumna[i][0][0] > kolumna[i][1][1]) {
czy1 = false;
break;
}
przedzial[i] = {kolumna[i][0][0] + 1, kolumna[i][1][1]};
}
// if (czy1) {
// cout << "TAK1" << '\n';
// cout << "d = " << d << '\n';
// rep(i, n) {
// cout << przedzial[i].st << " " << przedzial[i].nd << '\n';
// }
// }
rep(i, n) {
if (przedzial[i].nd < wys) {
wys = MAXN;
}
else {
wys = max(przedzial[i].st, wys);
}
// cout << "wys2 = " << wys2 << '\n';
if (przedzial[i].st > wys2) {
wys2 = -1;
}
else {
wys2 = min(wys2, przedzial[i].nd);
}
}
// cout << wys2 << '\n';
if (wys == MAXN && wys2 == -1) {
czy1 = false;
}
bool czy2 = true;
wys = 0;
wys2 = MAXN;
rep(i, n) {
if (kolumna[i][0][1] < kolumna[i][1][0]) {
czy2 = false;
break;
}
przedzial[i] = {kolumna[i][1][0] + 1, kolumna[i][0][1]};
}
// if (czy2) {
// cout << "TAK2" << '\n';
// cout << "d = " << d << '\n';
// rep(i, n) {
// cout << przedzial[i].st << " " << przedzial[i].nd << '\n';
// }
// }
rep(i, n) {
if (przedzial[i].nd < wys) {
wys = MAXN;
}
else {
wys = max(przedzial[i].st, wys);
}
if (przedzial[i].st > wys2) {
wys2 = -1;
}
else {
wys2 = min(wys2, przedzial[i].nd);
}
}
if (wys == MAXN && wys2 == -1) {
czy2 = false;
}
if (czy1 || czy2) {
return true;
}
return false;
}
bool por(trojka a, trojka b) {
return a.a < b.a;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
int mini = 1e9 + 1;
int maks = -1;
rep(i, n) {
rep(j, m) {
cin >> T[i][j];
v.pb({i, j, T[i][j]});
mini = min(mini, T[i][j]);
maks = max(maks, T[i][j]);
}
}
sort(v.begin(), v.end(), por);
int ans = maks - mini;
int poc = 0;
int kon = ans;
while (poc < kon) {
int sr = (poc + kon)/2;
if (spr(sr)) {
ans = sr;
kon = sr;
}
else {
poc = sr + 1;
}
}
cout << ans << '\n';
return 0;
}
