#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;
bool check_p(int diff) {
int mx_col = w;
for (int row = 1; row <= h; row++) {
int mn = a[row][1], mx = a[row][1];
int col;
for (col = 1; col < mx_col; col++) {
if (max(mx, a[row][col+1]) - min(mn, a[row][col+1]) > diff) break;
mn = min(mn, a[row][col+1]);
mx = max(mx, a[row][col+1]);
}
mx_col = col;
mn = 1e9; mx = 0;
for (col = col + 1; col <= w; col++) {
mn = min(mn, a[row][col]);
mx = max(mx, a[row][col]);
}
if (mx - mn > diff) return false;
}
return true;
}
bool check_n(int diff) {
int mn_col = 1;
for (int row = 1; row <= h; row++) {
int mn = a[row][w], mx = a[row][w];
int col;
for (col = w; col > mn_col; col--) {
if (max(mx, a[row][col-1]) - min(mn, a[row][col-1]) > diff) break;
mn = min(mn, a[row][col-1]);
mx = max(mx, a[row][col-1]);
}
mn_col = col;
mn = 1e9; mx = 0;
for (col = col - 1; col >= 1; col--) {
mn = min(mn, a[row][col]);
mx = max(mx, a[row][col]);
}
if (mx - mn > diff) return false;
}
return true;
}
bool check(int diff) {
return check_p(diff) || check_n(diff);
}
signed main() {
fastio;
cin >> h >> w;
for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> 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;
}
