#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = int;
using ld = long double;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using pq = priority_queue<T, vector<T>, greater<T>>;
const ll INF = 1e9 + 1;
ll MOD = 1e5 + 1;
ll MAXn = 2e6;
ll lg = 22;
const ld ap = 1e-6;
const double pi = acos(-1);
using rc = complex<double>;
template<class T>
istream &operator>>(istream &in, vector<T> &x) {
for (auto &i : x) {
in >> i;
}
return in;
}
template<class T>
ostream &operator<<(ostream &out, vector<T> &x) {
for (auto &i : x) {
out << i << ' ';
}
return out;
}
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
bool check(ll n, ll m, vector<vector<ll>> is) {
ll f = max(0, is[0][0]);
ll pr = m;
for (ll i = 0; i < n; i++) {
ll lst = -1;
if (is[i][0] == 0) lst = 0;
if (is[i][0] == -1) {
is[i][0] = f;
}
ll cn = is[i][0] == 0;
for (ll j = 1; j < m; j++) {
if (is[i][j] == 0) lst = j;
if (is[i][j] != -1) {
is[i][j] ^= f;
} else {
is[i][j] = is[i][j - 1];
}
if (is[i][j - 1] == 1 && is[i][j] == 0) return 0;
if (is[i][j] == 0) cn++;
}
if (lst + 1 > pr) return 0;
pr = min(pr, cn);
}
return 1;
}
void rotate(ll &n, ll &m, vector<vector<ll>> &is) {
vector<vector<ll>> res(m, vector<ll>(n));
for (ll i = 0; i < m; i++) {
for (ll j = 0; j < n; j++) {
res[i][j] = is[n - j - 1][i];
}
}
is = res;
swap(n, m);
}
void viperr() {
ll n, m;
cin >> n >> m;
vector<vector<ll>> a(n, vector<ll>(m));
for (auto &i : a) cin >> i;
ll mn = INF, mx = -INF;
for (auto i : a) {
for (auto j : i) {
mn = min(mn, j);
mx = max(mx, j);
}
}
ll l = -1, r = 1e9;
while (r - l > 1) {
ll x = (r + l) / 2;
vector<vector<ll>> is(n, vector<ll>(m, -1));
bool iss = 0;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
if (a[i][j] > mn + x && a[i][j] < mx - x) iss = 1;
if (a[i][j] <= mn + x && a[i][j] < mx - x) {
is[i][j] = 0;
} else if (a[i][j] >= mx - x && a[i][j] > mn + x) {
is[i][j] = 1;
}
}
}
if (iss) {
l = x;
continue;
}
bool res = check(n, m, is);
rotate(n, m, is);
res |= check(n, m, is);
rotate(n, m, is);
res |= check(n, m, is);
rotate(n, m, is);
res |= check(n, m, is);
rotate(n, m, is);
if (res) r = x;
else l = x;
}
cout << r;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t11 = 1;
// cin >> t11;
while (t11--) {
viperr();
cout << '\n';
}
return 0;
}
