#include <bits/stdc++.h>
using namespace std;
void solve() {
int H, W;
cin >> H >> W;
vector<vector<int>> A(H, vector<int>(W));
vector<pair<int, int>> P;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
P.emplace_back(i, j);
cin >> A[i][j];
}
}
int ans = INT_MAX;
for (int r = 0; r < 2; r++) {
sort(P.begin(), P.end(), [&](pair<int, int> x, pair<int, int> y) {
return A[x.first][x.second] < A[y.first][y.second];
});
vector<vector<int>> x(H, vector<int>(W + 1));
for (int i = 0; i < H; i++) {
x[i][W] = INT_MAX;
for (int j = W - 1; j >= 0; j--) {
x[i][j] = min(x[i][j + 1], A[i][j]);
}
}
multiset<int> Spref, Ssuff;
for (int i = 0; i < H; i++) {
Spref.insert(x[i][0]);
Ssuff.insert(x[i][0]);
}
vector<int> height(H), pref(H), suff(H);
vector<vector<bool>> used(H, vector<bool>(W, false));
ans = min(ans, A[P.back().first][P.back().second] - A[P[0].first][P[0].second]);
for (int i = 0; i < H * W - 1; i++) {
auto [u, v] = P[i];
used[u][v] = true;
for (int j = height[u]; j < W; j++) {
if (!used[u][j]) {
break;
}
height[u]++;
}
int p = u == 0 ? INT_MAX : pref[u - 1];
for (int j = u; j < H; j++) {
p = min(p, height[j]);
if (pref[j] == p) {
break;
}
Spref.erase(Spref.find(x[j][pref[j]]));
pref[j] = p;
Spref.insert(x[j][pref[j]]);
}
int s = u == H - 1 ? INT_MAX : suff[u + 1];
for (int j = u; j >= 0; j--) {
s = min(s, height[j]);
if (suff[j] == s) {
break;
}
Ssuff.erase(Ssuff.find(x[j][suff[j]]));
suff[j] = s;
Ssuff.insert(x[j][suff[j]]);
}
ans = min(ans, max(A[u][v] - A[P[0].first][P[0].second], A[P.back().first][P.back().second] - max(*Spref.begin(), *Ssuff.begin())));
}
for (int i = 0; i < H; i++) {
reverse(A[i].begin(), A[i].end());
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
