#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 2048;
int a[N][N];
int n, m;
int len[N];
bool can_extend(int i, int mx)
{
if (i > 0 && len[i-1] <= len[i])
return 0;
if (len[i] == m || a[i][len[i]] > mx)
return 0;
return 1;
}
int solve()
{
static bool col[N][N];
int mn1v = 2e9, mx1v = -1, mn2 = 0, mx2 = n*m-1;
vector<pair<int,pii>> alts;
memset(len, 0, sizeof(len));
Loop (i,0,n) Loop (j,0,m) {
alts.push_back({a[i][j], {i, j}});
col[i][j] = 1;
}
sort(alts.begin(), alts.end());
int ans = 2e9;
for (auto [mx, pos] : alts) {
int row = pos.first;
Loop (r,row,n) {
if (!can_extend(r, mx))
break;
while (can_extend(r, mx)) {
mx1v = max(mx1v, a[r][len[r]]);
mn1v = min(mn1v, a[r][len[r]]);
col[r][len[r]] = 0;
len[r]++;
}
}
for (; mn2 < n*m && !col[alts[mn2].second.first][alts[mn2].second.second]; ++mn2);
for (; mx2 >= 0 && !col[alts[mx2].second.first][alts[mx2].second.second]; --mx2);
if (mx1v == -1 || mx2 == -1)
continue;
ans = min(ans, max(mx1v - mn1v, alts[mx2].first - alts[mn2].first));
}
return ans;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,n) Loop (j,0,m)
cin >> a[i][j];
int ans = 2e9;
ans = min(ans, solve());
Loop (i,0,n/2) Loop (j,0,m)
swap(a[i][j], a[n-1-i][j]);
ans = min(ans, solve());
Loop (i,0,n) Loop (j,0,m/2)
swap(a[i][j], a[i][m-1-j]);
ans = min(ans, solve());
Loop (i,0,n/2) Loop (j,0,m)
swap(a[i][j], a[n-1-i][j]);
ans = min(ans, solve());
cout << ans << '\n';
}
