#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
const int N = 2000;
int A[N][N];
int pref[N+1];
int n, m;
vector<pair<int,int>> mns = {{1e9, 1e9}}, mxs = {{0, 0}};
void add(int x) {
int y = min(mns.back().second, x);
mns.emplace_back(x, y);
y = max(mxs.back().second, x);
mxs.emplace_back(x, y);
}
void pop() {
mns.pop_back();
mxs.pop_back();
}
int range() {
return mxs.back().second - mns.back().second;
}
void clear() {
mns.resize(1);
mxs.resize(1);
}
bool check(int k) {
pref[n] = m;
for (int i = n-1; i >= 0; i--) {
pref[i] = pref[i+1];
for (int j = 0; j < pref[i]; j++)
add(A[i][j]);
while (pref[i] > 0 && range() > k) {
--pref[i];
pop();
}
}
// cout << k << "\n";
// for (int i = 0; i < n; i++)
// cout << pref[i] << "\n";
int mnother = 1e9, mxother = 0;
for (int i = 0; i < n; i++) {
if (pref[i] == m) continue;
mnother = min(mnother, *min_element(A[i] + pref[i], A[i] + m));
mxother = max(mxother, *max_element(A[i] + pref[i], A[i] + m));
}
// cout << mnother << " " << mxother << "\n";
// cout << "\n";
clear();
return mxother - mnother <= k;
}
int solve() {
int l = -1, r = 1e9;
while (l+1 < r) {
int mid = (l+r)/2;
(check(mid) ? r : l) = mid;
}
return r;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) for (int j = 0; j < m; cin >> A[i][j++]);
int ans = solve();
for (int i = 0; i < n; i++)
reverse(A[i], A[i] + m);
ans = min(ans, solve());
cout << ans;
}
