// Why I am so dumb? :c
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = (int)2e3 + 3;
pair<int, int> pref[MAXN][MAXN];
pair<int, int> suff[MAXN][MAXN];
int newArr[MAXN][MAXN];
int arr[MAXN][MAXN];
int rl[MAXN * MAXN];
int n, m, k, ans;
void compress() {
vector<int> vv;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
vv.pb(arr[i][j]);
}
}
sort(all(vv));
vv.resize(unique(all(vv)) - vv.begin());
k = vv.size();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int ps = upper_bound(all(vv), arr[i][j]) - vv.begin();
rl[ps] = arr[i][j];
arr[i][j] = ps;
}
}
}
bool goPrefL(int lim) {
int ptr = m, cur = 0, cur2 = 0;
for (int i = 1; i <= n; ++i) {
while (ptr > 0 && pref[i][ptr].se < lim) {
--ptr;
}
if (ptr < 1) {
break;
}
cur = max(cur, pref[i][ptr].fi);
if (ptr < m) {
cur2 = max(cur2, suff[i][ptr + 1].fi);
}
}
if (ptr > 0 && cur == k) {
ans = min(ans, max(rl[k] - rl[lim], rl[cur2] - rl[1]));
return 1;
}
return 0;
}
bool goSuffL(int lim) {
int ptr = 1, cur = 0, cur2 = 0;
for (int i = 1; i <= n; ++i) {
while (ptr <= m && suff[i][ptr].se < lim) {
++ptr;
}
if (ptr > m) {
break;
}
cur = max(cur, suff[i][ptr].fi);
if (ptr > 1) {
cur2 = max(cur2, pref[i][ptr - 1].fi);
}
}
if (ptr <= m && cur == k) {
ans = min(ans, max(rl[k] - rl[lim], rl[cur2] - rl[1]));
return 1;
}
return 0;
}
bool goPrefR(int lim) {
int ptr = m, cur = k + 1, cur2 = k + 1;
for (int i = 1; i <= n; ++i) {
while (ptr > 0 && pref[i][ptr].fi > lim) {
--ptr;
}
if (ptr < 1) {
break;
}
cur = min(cur, pref[i][ptr].se);
if (ptr < m) {
cur2 = min(cur2, suff[i][ptr + 1].se);
}
}
if (ptr > 0 && cur == 1) {
ans = min(ans, max(rl[lim] - rl[1], rl[k] - rl[cur2]));
return 1;
}
return 0;
}
bool goSuffR(int lim) {
int ptr = 1, cur = k + 1, cur2 = k + 1;
for (int i = 1; i <= n; ++i) {
while (ptr <= m && suff[i][ptr].fi > lim) {
++ptr;
}
if (ptr > m) {
break;
}
cur = min(cur, suff[i][ptr].se);
if (ptr > 1) {
cur2 = min(cur2, pref[i][ptr - 1].se);
}
}
if (ptr <= m && cur == 1) {
ans = min(ans, max(rl[lim] - rl[1], rl[k] - rl[cur2]));
return 1;
}
return 0;
}
void solve() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &arr[i][j]);
}
}
compress();
// fi -> max, se -> min
ans = rl[k] - rl[1];
for (int step = 0; step < 4; ++step) {
for (int i = 1; i <= n; ++i) {
pref[i][1] = mp(arr[i][1], arr[i][1]);
suff[i][m] = mp(arr[i][m], arr[i][m]);
for (int j = 2; j <= m; ++j) {
pref[i][j].fi = max(pref[i][j - 1].fi, arr[i][j]);
pref[i][j].se = min(pref[i][j - 1].se, arr[i][j]);
}
for (int j = m - 1; j > 0; --j) {
suff[i][j].fi = max(suff[i][j + 1].fi, arr[i][j]);
suff[i][j].se = min(suff[i][j + 1].se, arr[i][j]);
}
}
for (int i = 2; i <= k; ++i) {
if (!goPrefL(i)) {
break;
}
}
for (int i = 2; i <= k; ++i) {
if (!goSuffL(i)) {
break;
}
}
for (int i = k - 1; i > 0; --i) {
if (!goPrefR(i)) {
break;
}
}
for (int i = k - 1; i > 0; --i) {
if (!goSuffR(i)) {
break;
}
}
// rotate array
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
newArr[m - j + 1][i] = arr[i][j];
}
}
swap(n, m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
arr[i][j] = newArr[i][j];
}
}
}
printf("%d\n", ans);
}
int main() {
int tt = 1;
while (tt--) {
solve();
}
return 0;
}
