#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
const int MAX = 2010;
int n, m;
int arr[MAX][MAX];
int pmax[MAX][MAX], pmin[MAX][MAX], smax[MAX][MAX], smin[MAX][MAX];
int gmax, gmin;
bool check(int lmin, int lmax, int rmin, int rmax){
//bool owo = 0;
//if(lmin == 5 and lmax == 23 and rmin == 10 and rmax == 28) owo = 1;
bool ret = 0;
int ptr = m;
int curmin = INF, curmax = -INF;
FOR(i, 1, n, 1){
while(pmin[i][ptr] < lmin or lmax < pmax[i][ptr]){
ptr--;
assert(ptr >= 0);
}
curmin = min(curmin, smin[i][ptr + 1]);
curmax = max(curmax, smax[i][ptr + 1]);
//if(owo) cerr<<"i = "<<i<<" : ptr = "<<ptr<<endl;
}
if(rmin <= curmin and curmax <= rmax) ret = 1;
ptr = m;
curmin = INF, curmax = -INF;
for(int i = n; i >= 1; i--){
while(pmin[i][ptr] < lmin or lmax < pmax[i][ptr]){
ptr--;
assert(ptr >= 0);
}
curmin = min(curmin, smin[i][ptr + 1]);
curmax = max(curmax, smax[i][ptr + 1]);
//if(owo) cerr<<"i = "<<i<<" : ptr = "<<ptr<<endl;
}
if(rmin <= curmin and curmax <= rmax) ret = 1;
return ret;
}
bool CHECK(int T){
return (check(gmin, gmin + T, gmax - T, gmax) or check(gmax - T, gmax, gmin, gmin + T));
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
FOR(i, 1, n, 1){
FOR(j, 1, m, 1){
cin>>arr[i][j];
}
}
//cerr<<"ok"<<endl;
gmax = -INF;
gmin = INF;
FOR(i, 1, n, 1){
pmax[i][0] = -INF;
pmin[i][0] = INF;
FOR(j, 1, m, 1){
pmax[i][j] = max(pmax[i][j-1], arr[i][j]);
pmin[i][j] = min(pmin[i][j-1], arr[i][j]);
gmax = max(gmax, arr[i][j]);
gmin = min(gmin, arr[i][j]);
}
smax[i][m+1] = -INF;
smin[i][m+1] = INF;
for(int j = m; j >= 1; j--){
smax[i][j] = max(smax[i][j+1], arr[i][j]);
smin[i][j] = min(smin[i][j+1], arr[i][j]);
}
}
//cerr<<"ok"<<endl;
int L = 0, R = gmax - gmin, mid;
while(L < R){
mid = (L + R) / 2;
if(CHECK(mid)) R = mid;
else L = mid + 1;
//cerr<<"CHECK("<<mid<<") = "<<CHECK(mid)<<endl;
}
cout<<L<<'\n';
return 0;
}
