#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
int mn = 1e9, mx = 0;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
cin >> a[i][j];
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
}
int l = 0, r = 1e9, ans = -1;
auto check = [&](int mid) {
int lst = -1, ok = 1;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
if (a[i][j] > mn + mid)
lst = max(lst, j);
}
for (int j = 0;j < m;j++) {
if (j <= lst && a[i][j] < mx - mid)
ok = 0;
}
}
if (ok)
return ok;
reverse(a.begin(), a.end());
lst = -1;
ok = 1;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
if (a[i][j] > mn + mid)
lst = max(lst, j);
}
for (int j = 0;j < m;j++) {
if (j <= lst && a[i][j] < mx - mid)
ok = 0;
}
}
if (ok)
return ok;
for (int i = 0;i < n;i++)
reverse(a[i].begin(), a[i].end());
lst = -1;
ok = 1;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
if (a[i][j] > mn + mid)
lst = max(lst, j);
}
for (int j = 0;j < m;j++) {
if (j <= lst && a[i][j] < mx - mid)
ok = 0;
}
}
if (ok)
return ok;
reverse(a.begin(), a.end());
lst = -1;
ok = 1;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
if (a[i][j] > mn + mid)
lst = max(lst, j);
}
for (int j = 0;j < m;j++) {
if (j <= lst && a[i][j] < mx - mid)
ok = 0;
}
}
return ok;
};
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
cout << ans << '\n';
}
return 0;
}
