#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
constexpr bool typetest = 0;
constexpr int N = 2e3 + 5;
const int Inf = 1e9 + 7;
int m, n, maxn(-Inf);
int a[N][N], b[N][N], smin[N][N], smax[N][N];
int pmin[N][N], pmax[N][N], s[N], p[N];
void Read()
{
cin >> m >> n;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
{
cin >> a[i][j];
maxn = max(maxn, a[i][j]);
}
}
bool Check(int v)
{
for (int i = 1; i <= m; ++i)
{
s[i] = 0;
p[i] = n + 1;
for (int j = 1; j <= n; ++j)
if (a[i][j] < maxn - v)
{
p[i] = min(p[i], j);
s[i] = max(s[i], j);
}
}
int maxx(-Inf), minx(Inf), piv(n + 1);
for (int i = m; i; --i)
{
piv = min(piv, p[i]);
maxx = max(maxx, smax[i][piv]);
minx = min(minx, smin[i][piv]);
}
if (maxx - minx <= v)
return true;
maxx = -Inf;
minx = Inf;
piv = 0;
for (int i = 1; i <= m; ++i)
{
piv = max(piv, s[i]);
maxx = max(maxx, pmax[i][piv]);
minx = min(minx, pmin[i][piv]);
}
return (maxx - minx <= v);
}
int Cal()
{
for (int i = 1; i <= m; ++i)
{
smin[i][n + 1] = pmin[i][0] = Inf;
smax[i][n + 1] = pmax[i][0] = -Inf;
for (int j = 1; j <= n; ++j)
{
pmin[i][j] = min(a[i][j], pmin[i][j - 1]);
pmax[i][j] = max(a[i][j], pmax[i][j - 1]);
}
for (int j = n; j; --j)
{
smin[i][j] = min(smin[i][j + 1], a[i][j]);
smax[i][j] = max(smax[i][j + 1], a[i][j]);
}
}
//cerr << "ok !\n";
int l = 0, mid, h = maxn;
while (l <= h)
{
mid = (l + h) / 2;
if (Check(mid))
h = mid - 1;
else
l = mid + 1;
}
return l;
}
void Solve()
{
int ans = Cal();
//cerr << "ok ? \n";
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
b[n - j + 1][i] = a[i][j];
swap(m, n);
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
a[i][j] = b[i][j];
cout << min(ans, Cal());
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t(1);
if (typetest)
cin >> t;
for (int _ = 1; _ <= t; ++_)
{
Read();
Solve();
}
}
