#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define mp make_pair
#define int ll
const int MAXN = 2e3 + 5;
int a[MAXN][MAXN];
int h, w;
int mini, maxi;
bool check(int diff) {
vector<int> left_has_mx(h+1), left_has_mn(h+1), right_has_mx(h+1), right_has_mn(h+1);
for (int i = 1; i <= h; i++) {
int l = 0;
while (l < w && a[i][l + 1] <= mini + diff) l++;
left_has_mn[i] = l;
l = 0;
while (l < w && a[i][l + 1] >= maxi - diff) l++;
left_has_mx[i] = l;
int r = w+1;
while (r > 1 && a[i][r - 1] <= mini + diff) r--;
right_has_mn[i] = r;
r = w+1;
while (r > 1 && a[i][r - 1] >= maxi - diff) r--;
right_has_mx[i] = r;
}
// left has max, decreasing l
bool good = true;
int mx_l = w;
for (int i = 1; i <= h && good; i++) {
mx_l = min(mx_l, left_has_mx[i]);
int r = max(mx_l + 1, right_has_mn[i]);
if (r > mx_l + 1) good = false;
}
if (good) return true;
// left has min, decreasing l
good = true;
mx_l = w;
for (int i = 1; i <= h && good; i++) {
mx_l = min(mx_l, left_has_mn[i]);
int r = max(mx_l + 1, right_has_mx[i]);
if (r > mx_l + 1) good = false;
}
if (good) return true;
// left has max, increasing r
good = true;
int mn_r = 1;
for (int i = 1; i <= h && good; i++) {
mn_r = max(mn_r, right_has_mn[i]);
int l = min(mn_r - 1, left_has_mx[i]);
if (l < mn_r - 1) good = false;
}
if (good) return true;
// left has max, increasing r
good = true;
mn_r = 1;
for (int i = 1; i <= h && good; i++) {
mn_r = max(mn_r, right_has_mx[i]);
int l = min(mn_r - 1, left_has_mn[i]);
if (l < mn_r - 1) good = false;
}
return good;
}
signed main() {
fastio;
cin >> h >> w;
mini = 1e9, maxi = 0;
for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) {
cin >> a[i][j];
mini = min(mini, a[i][j]);
maxi = max(maxi, a[i][j]);
}
int l = 0, r = 1e9;
while (l < r) {
int mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
