#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sh short
const int N = 2e3+110;
const int INF = 1e9;
int a[N][N], cnt[N], h, w;
vector<int> v;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
gp_hash_table<long long, int, custom_hash> hs;
void fs(int &number) {
register int c;
number = 0;
c = getchar();
for (; (c>47 && c<58); c=getchar()) number = number *10 + c - 48;
}
bool cmp(sh x, sh y) {
return a[cnt[x]+1][x] > a[cnt[y]+1][y];
}
deque<int> tmp;
int solve() {
memset(cnt, 0, sizeof(cnt));
hs.clear();
int res=INF, lis=INF, uis=-1;
deque<int> q=tmp;
priority_queue<sh, vector<sh>, function<bool(sh, sh)>> pq(cmp);
pq.push(w);
for (int k=0; k<(int)v.size(); ++k) {
while (!pq.empty()) {
if (a[cnt[pq.top()]+1][pq.top()] <= v[k]) {
sh x=pq.top(); pq.pop();
int val=a[cnt[x]+1][x]; ++hs[val];
lis=min(lis, val), uis=max(uis, val);
++cnt[x];
if (cnt[x] == h) continue;
if (x == w || cnt[x+1] >= cnt[x]+1) pq.push(x);
if (x == 1) continue;
if (cnt[x] == cnt[x-1]+1) pq.push(x-1);
} else break;
}
while (!q.empty()) {
if (hs[q.front()] > 0) --hs[q.front()], q.pop_front();
else break;
}
while (!q.empty()) {
if (hs[q.back()] > 0) --hs[q.back()], q.pop_back();
else break;
}
int lf;
if (q.empty()) lf=INF;
else lf=q.back()-q.front();
res=min(res, max(lf, uis-lis));
}
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);
fs(h), fs(w);
for (int i=1; i<=h; ++i) {
for (int j=1; j<=w; ++j) {
fs(a[i][j]);
v.push_back(a[i][j]);
}
} sort(v.begin(), v.end());
for (auto u : v) tmp.push_back(u);
v.erase(unique(v.begin(), v.end()), v.end());
int ans=solve();
hor(); ans=min(ans, solve()); hor();
ver();
ans=min(ans, solve());
hor(); ans=min(ans, solve()); hor();
printf("%d\n", ans);
}
