#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define INF (int)(1e18)
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 2010;
int a[MAXN][MAXN];
int tmp[MAXN][MAXN];
int r[MAXN];
int l[MAXN];
// rotate CCW once
void rot(int &n, int &m) {
For(i, 0, n - 1) For(j, 0, m - 1) {
tmp[m - j - 1][i] = a[i][j];
}
swap(n, m);
For(i, 0, n - 1) For(j, 0, m - 1) {
a[i][j] = tmp[i][j];
}
}
void check1(int n, int m, int lo) {
For(i, 0, n - 1) {
r[i] = -1;
for(; r[i] + 1 < m && a[i][r[i] + 1] >= lo; r[i]++);
if(i) r[i] = min(r[i], r[i - 1]);
}
}
void check2(int n, int m, int hi) {
Forr(i, n - 1, 0) {
l[i] = m;
for(; l[i] - 1 >= 0 && a[i][l[i] - 1] <= hi; l[i]--);
if(i < n - 1) l[i] = max(l[i], l[i + 1]);
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
// =^-w-^=
int n, m; cin >> n >> m;
int mx = -1, mn = INF;
For(i, 0, n - 1) For(j, 0, m - 1) {
cin >> a[i][j];
mx = max(mx, a[i][j]);
mn = min(mn, a[i][j]);
}
int ans = INF;
For(_, 0, 3) {
int hi = mx - mn;
int lo = -1;
while(hi - lo > 1) {
int mi = (hi + lo) / 2;
check1(n, m, mx - mi);
check2(n, m, mn + mi);
bool ok = true;
For(i, 0, n - 1) {
if(r[i] + 1 < l[i]) {
ok = false;
break;
}
}
if(ok) hi = mi;
else lo = mi;
}
ans = min(ans, hi);
rot(n, m);
}
cout << ans << "\n";
return 0;
}
