// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 2e3 + 5;
const int M = 1 << 10;
const int K = 19;
const int LG = 11;
const int INF = 2e9 + 5;
const int C = 26;
const int B = 1000;
const int MOD = 998244353;
int n, m, mp[N][N], prefmx[N][N], suffmx[N][N], prefmn[N][N], suffmn[N][N], mnv, mxv;
inline void solve()
{
cin >> n >> m;
mnv = INF;
mxv = 0;
for (int x = 0; x <= n + 1; x++)
{
for (int y = 0; y <= m + 1; y++)
{
prefmn[x][y] = suffmn[x][y] = INF;
prefmx[x][y] = suffmx[x][y] = 0;
}
}
for (int x = 1; x <= n; x++)
{
for (int y = 1; y <= m; y++)
{
cin >> mp[x][y];
mnv = min(mnv, mp[x][y]);
mxv = max(mxv, mp[x][y]);
}
}
for (int x = 1; x <= n; x++)
{
for (int y = 1; y <= m; y++)
{
prefmx[x][y] = max(prefmx[x][y - 1], mp[x][y]);
prefmn[x][y] = min(prefmn[x][y - 1], mp[x][y]);
}
for (int y = m; y >= 1; y--)
{
suffmx[x][y] = max(suffmx[x][y + 1], mp[x][y]);
suffmn[x][y] = min(suffmn[x][y + 1], mp[x][y]);
}
}
int l = 0, r = INF, ans = 0;
while (l <= r)
{
int mid = (l + r) / 2, mx = 0, mn = INF, last = m;
bool b = 0;
int i = mid;
for (int x = 1; x <= n; x++)
{
while (last > 0)
{
if (prefmx[x][last] > i)
{
// cout << prefmx[x][last] << " " << i << "\n";
last--;
}
else
{
break;
}
}
// cout << last << " " << x << "pos\n";
mx = max(mx, suffmx[x][last + 1]);
mn = min(mn, suffmn[x][last + 1]);
}
// cout << mx << " " << mn << "v\n";
if (mx - mn <= mid && mn != INF)
{
b = 1;
}
mx = 0, mn = INF, last = 1;
for (int x = 1; x <= n; x++)
{
while (last <= m)
{
if (suffmx[x][last] > i)
{
last++;
}
else
{
break;
}
}
mx = max(mx, prefmx[x][last - 1]);
mn = min(mn, prefmn[x][last - 1]);
}
if (mx - mn <= mid && mn != INF)
{
b = 1;
}
mx = 0, mn = INF, last = m;
for (int x = n; x >= 1; x--)
{
while (last > 0)
{
if (prefmx[x][last] > i)
{
last--;
}
else
{
break;
}
}
mx = max(mx, suffmx[x][last + 1]);
mn = min(mn, suffmn[x][last + 1]);
}
if (mx - mn <= mid && mn != INF)
{
b = 1;
}
mx = 0, mn = INF, last = 1;
for (int x = n; x >= 1; x--)
{
while (last <= m)
{
if (suffmx[x][last] > i)
{
last++;
}
else
{
break;
}
}
mx = max(mx, prefmx[x][last - 1]);
mn = min(mn, prefmn[x][last - 1]);
}
if (mx - mn <= mid && mn != INF)
{
b = 1;
}
// cout << mid << " " << b << "\n";
if(b)
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
cout << ans - mnv << "\n";
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
for (int x = 1; x <= t; x++)
{
solve();
}
return 0;
}
