#include <bits/stdc++.h>
#include <experimental/random>
#include <random>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 1e18, MOD = 1e9 + 7;
void solve();
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int q = 1;
//cin >> q;
while (q--) {
solve();
}
}
vector<vector<ll>> a;
ll mx = -INF;
ll n, m;
bool check(ll delta) {
vector<vector<ll>> mn(n, vector<ll>(m + 1, INF));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mn[i][j + 1] = min(mn[i][j], a[i][j]);
}
}
vector<ll> hv;
ll prev = m;
for (int i = 0; i < n; i++) {
ll l = 0, r = m + 1;
while (r - l > 1) {
ll mid = (l + r) / 2;
if (mx - mn[i][mid] <= delta) {
l = mid;
} else {
r = mid;
}
}
prev = min(prev, l);
hv.push_back(prev);
}
ll m1 = -INF, m2 = INF;
for (int i = 0; i < n; i++) {
for (ll j = hv[i]; j < m; j++) {
m1 = max(m1, a[i][j]);
m2 = min(m2, a[i][j]);
}
}
return m1 - m2 <= delta;
}
void solve() {
cin >> n >> m;
a.resize(n, vector<ll>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
mx = max(mx, a[i][j]);
}
}
ll l = -1, r = INF;
while (r - l > 1) {
ll mid = (l + r) / 2;
if (check(mid)) {
r = mid;
continue;
}
for (int i = 0; i < n; i++) {
reverse(a[i].begin(), a[i].end());
}
if (check(mid)) {
r = mid;
continue;
}
reverse(a.begin(), a.end());
if (check(mid)) {
r = mid;
continue;
}
for (int i = 0; i < n; i++) {
reverse(a[i].begin(), a[i].end());
}
if (check(mid)) {
r = mid;
continue;
}
reverse(a.begin(), a.end());
l = mid;
}
cout << r;
}
