#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int INF = 1e9;
void test_case() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n+1, vector<int>(m+1));
int mx = 0, mn = INF;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
cin >> a[i][j];
ckmax(mx, a[i][j]);
ckmin(mn, a[i][j]);
}
vector<ar<int, 3>> vals(8);
for (int i = 0; i < 8; i++) {
vals[i][0] = i >> 2 & 1;
vals[i][1] = i >> 1 & 1;
vals[i][2] = i & 1;
}
int ans = mx - mn;
// give the max/min to who
for (int A = 0; A < 2; A++) {
// !A = left has max, right has min
// A = left has min, right has max
vector<vector<int>> dp(8, vector<int>(m+1, INF));
auto conv = [](int vis_left, int vis_right, int order) {
return (vis_left << 2) + (vis_right << 1) + order;
};
// order = 0 ==> going right
dp[conv(0, 0, 0)][0] = 0;
dp[conv(0, 0, 1)][m] = 0;
for (int i = 1; i <= n; i++) {
vector<vector<int>> dp2(8, vector<int>(m+1, INF));
vector<bool> vleft(m+1), vright(m+1);
vector<int> pref(m+1, !A ? INF : -1), suff(m+1, !A ? -1 : INF);
for (int j = 1; j <= m; j++) {
vleft[j] = (a[i][j] == (A ? mn : mx)) || vleft[j-1];
if (!A) pref[j] = min(a[i][j], pref[j-1]);
else pref[j] = max(a[i][j], pref[j-1]);
}
for (int j = m-1; j >= 0; j--) {
vright[j] = (a[i][j+1] == (A ? mx : mn)) || vright[j+1];
if (!A) suff[j] = max(a[i][j+1], suff[j+1]);
else suff[j] = min(a[i][j+1], suff[j+1]);
}
if (!A) { // maximize for left, minimize for right
pref[0] = mx, suff[m] = mn;
}
else {
pref[0] = mn, suff[m] = mx;
}
for (int j = 0; j < 8; j++) {
const auto& [vis_left, vis_right, order] = vals[j];
vector<int> pref_mn(m+1), suff_mn(m+1);
for (int k = 0; k <= m; k++) {
pref_mn[k] = min(dp[j][k], k ? pref_mn[k-1] : INF);
}
for (int k = m; k >= 0; k--) {
suff_mn[k] = min(dp[j][k], k+1 <= m ? suff_mn[k+1] : INF);
}
for (int k = 0; k <= m; k++) {
auto calc = [&]() {
if (!A) return max(mx - pref[k], suff[k] - mn);
return max(pref[k] - mn, mx - suff[k]);
};
if (!order) {
ckmin(dp2[conv(vis_left | vleft[k], vis_right | vright[k], order)][k], max(pref_mn[k], calc()));
}
else {
ckmin(dp2[conv(vis_left | vleft[k], vis_right | vright[k], order)][k], max(suff_mn[k], calc()));
}
}
}
swap(dp, dp2);
}
for (int i = 0; i < 2; i++) {
ckmin(ans, *min_element(all(dp[conv(1, 1, i)])));
}
}
cout << ans << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while (t--) test_case();
}
