#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, short>
const int N = 2e3+110;
const ll INF = 1e18;
ll a[N][N], cnt[N], h, w;
vector<ll> v;
ll solve() {
memset(cnt, 0, sizeof(cnt));
ll res=INF;
multiset<int> js, is;
for (int i=1; i<=h; ++i) {
for (int j=1; j<=w; ++j) js.insert(a[i][j]);
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({a[1][w], w});
for (int k=0; k<(int)v.size(); ++k) {
while (!pq.empty()) {
if (pq.top().first <= v[k]) {
pii x=pq.top(); pq.pop();
js.erase(js.find(x.first)), is.insert(x.first);
++cnt[x.second];
if (cnt[x.second] == h) continue;
if (x.second == w || cnt[x.second+1] >= cnt[x.second]+1) {
pq.push({a[cnt[x.second]+1][x.second], x.second});
}
if (x.second == 1) continue;
if (cnt[x.second] == cnt[x.second-1]+1) {
pq.push({a[cnt[x.second]][x.second-1], x.second-1});
}
} else break;
}
ll lf, rf;
if (js.empty()) lf=INF;
else lf=(*js.rbegin())-(*js.begin());
if (is.empty()) rf=INF;
else rf=(*is.rbegin())-(*is.begin());
res=min(res, max(lf, rf));
}
return res;
}
void hor() {
for (int i=1; i<h/2+1; ++i) {
for (int j=1; j<=w; ++j) swap(a[i][j], a[h-i+1][j]);
}
}
void ver() {
for (int i=1; i<=h; ++i) {
for (int j=1; j<w/2+1; ++j) swap(a[i][j], a[i][w-j+1]);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>h>>w;
for (int i=1; i<=h; ++i) {
for (int j=1; j<=w; ++j) {
cin>>a[i][j];
v.push_back(a[i][j]);
}
} sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
ll ans=solve();
hor(); ans=min(ans, solve()); hor();
ver();
ans=min(ans, solve());
hor(); ans=min(ans, solve()); hor();
cout<<ans<<"\n";
}
