#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()
{
multiset<int> s1, s2;
vector<pair<int,int>> alts;
memset(len, 0, sizeof(len));
Loop (i,0,n) Loop (j,0,m) {
alts.push_back({a[i][j], i});
s2.insert(a[i][j]);
}
sort(alts.begin(), alts.end());
int ans = 2e9;
for (auto [mx, row] : alts) {
Loop (r,row,n) {
if (!can_extend(r, mx))
break;
while (can_extend(r, mx)) {
s1.insert(a[r][len[r]]);
s2.erase(s2.find(a[r][len[r]]));
len[r]++;
}
}
if (s1.empty() || s2.empty())
continue;
ans = min(ans, max(*s1.rbegin() - *s1.begin(),
*s2.rbegin() - *s2.begin()));
}
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';
}
