#include <bits/stdc++.h>
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 2005;
int h, w, a[N][N], mn = inf, mni = -1, mnj = -1, mxh[N], mnLand[N], mx = -1;
bool testBoard(int direction, int x) {
if (direction == 0) {
if (mnLand[mnj] < mni) return false;
//Below area contains min, upper area contains max.
int mnInMaxLand = inf;
fw (j, 0, w) {
bw (i, h, mnLand[j] + 1) mnInMaxLand = min(mnInMaxLand, a[i][j]);
}
if (mx - mnInMaxLand <= x) return true;
return false;
} else {
if (mnLand[mnj] > mni) return false;
int mnInMaxLand = inf;
fw (j, 0, w) {
fw (i, 0, mnLand[j]) mnInMaxLand = min(mnInMaxLand, a[i][j]);
}
if (mx - mnInMaxLand <= x) return true;
return false;
}
}
bool check(int x) {
if (mx - mn <= x) return true;
//Fix below area as land that contains the min element.
fw (j, 0, w) {
mxh[j] = -1;
fw (i, 0, h) {
if (a[i][j] > mn + x) break;
mxh[j] = i;
}
}
if (mxh[mnj] >= mni) {
int curMx = h - 1;
fw (j, 0, w) {
//Make it decreasing from left to right.
mnLand[j] = min(curMx, mxh[j]);
curMx = min(curMx, mxh[j]);
}
if (testBoard(0, x)) return true;
curMx = h - 1;
bw (j, w, 0) {
//Make it decreasing from left to right.
mnLand[j] = min(curMx, mxh[j]);
curMx = min(curMx, mxh[j]);
}
if (testBoard(0, x)) return true;
}
//Fix above area
fw (j, 0, w) {
mxh[j] = h;
bw (i, h, 0) {
if (a[i][j] > mn + x) break;
mxh[j] = i;
}
}
if (mxh[mnj] <= mni) {
int curMx = 0;
fw (j, 0, w) {
//Make it decreasing from left to right.
mnLand[j] = max(curMx, mxh[j]);
curMx = max(curMx, mxh[j]);
}
if (testBoard(1, x)) return true;
curMx = 0;
bw (j, w, 0) {
//Make it decreasing from left to right.
mnLand[j] = max(curMx, mxh[j]);
curMx = max(curMx, mxh[j]);
}
if (testBoard(1, x)) return true;
}
return false;
}
signed main() {
#ifdef BLU
in("blu.inp");
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> h >> w;
fw (i, 0, h) fw (j, 0, w) cin >> a[i][j];
fw (i, 0, h) fw (j, 0, w) {
if (a[i][j] < mn) {
mn = a[i][j];
mni = i, mnj = j;
}
mx = max(mx, a[i][j]);
}
int l = 0, r = 1e9;
while (l < r) {
int m = (l + r) >> 1;
if (check(m)) r = m;
else l = m + 1;
}
cout << l;
return 0;
}
