#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()
using namespace std;
using PQ = priority_queue<int, vector<int>, greater<int>>;
const int INF = 2e18;
const int maxn = 2e3 + 5;
const int M = 1e9 + 7;
int n, m, mx, mn;
int a[maxn][maxn];
int g[maxn][maxn];
void rotate () {
// (3, 2) -> (2, 3)
// (X, Y) -> (n - Y + 1, X)
// (Y, X) -> (X, n - Y + 1)
// (1, 4) -> (2, 3)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
g[j][n - i + 1] = a[i][j];
}
}
swap (n, m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = g[i][j];
}
}
}
int check (int x) {
int lim = m + 1;
for (int i = 1; i <= n; i++) {
int r = 0;
for (int j = 1; j <= min (lim, m); j++) {
if (mx - x <= a[i][j]) r = max (r, j);
else break;
}
lim = r;
for (int j = r + 1; j <= m; j++) {
if (a[i][j] - x > mn) return 0;
}
}
return 1;
}
int search () {
int l = 0, r = 2e9 + 5;
while (l < r) {
int mid = (l + r) >> 1;
if (check (mid)) r = mid;
else l = mid + 1;
}
return r;
}
void init () {
cin >> n >> m;
mx = -INF, mn = INF;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
mx = max (mx, a[i][j]);
mn = min (mn, a[i][j]);
}
}
}
void solve () {
int ans = INF;
ans = min (ans, search ());
rotate ();
ans = min (ans, search ());
rotate ();
ans = min (ans, search ());
rotate ();
ans = min (ans, search ());
cout << ans << "\n";
}
signed main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
init();
solve();
}
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
*/
