#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) {
// minimum on left, maximum on right
// left decreases
int mx_col = w;
bool good = true;
for (int row = 1; row <= h && good; row++) {
int col;
for (col = 0; col < mx_col; col++) {
if (a[row][col+1] > mini + diff) break;
}
mx_col = col;
int mn = 1e9;
for (col = col + 1; col <= w; col++) {
mn = min(mn, a[row][col]);
}
if (mn < maxi - diff) good = false;
}
if (good) return true;
// right decreases
int mn_col = 0;
good = true;
for (int row = 1; row <= h && good; row++) {
int col;
for (col = w+1; col > mn_col; col--) {
if (a[row][col-1] < maxi - diff) break;
}
mn_col = col;
int mx = 0;
for (col = col - 1; col > 0; col--) {
mx = max(mx, a[row][col]);
}
if (mx > mini + diff) good = false;
}
if (good) return true;
// maximum on left, minimum on right
// left decreases
mx_col = w;
good = true;
for (int row = 1; row <= h && good; row++) {
int col;
for (col = 0; col < mx_col; col++) {
if (a[row][col+1] < maxi - diff) break;
}
mx_col = col;
int mx = 0;
for (col = col + 1; col <= w; col++) {
mx = max(mx, a[row][col]);
}
if (mx > mini + diff) good = false;
}
if (good) return true;
// right decreases
mn_col = 0;
good = true;
for (int row = 1; row <= h && good; row++) {
int col;
for (col = w+1; col > mn_col; col--) {
if (a[row][col-1] > mini + diff) break;
}
mn_col = col;
int mn = 0;
for (col = col - 1; col > 0; col--) {
mn = min(mn, a[row][col]);
}
if (mn < maxi - diff) 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;
}
