#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define S second
#define F first
#define pb push_back
#define for1(n) for(int i=1;i<=n;i++)
#define for0(n) for(int i=0;i<n;i++)
#define endl '\n'
#define Mp make_pair
#define all(x) x.begin(),x.end()
const ll mod=1e9+7;
const ll inf=1e18+10;
const int N=2e3+10;
int A[N][N],B[N],C[N],D[N],n,m,q,k,dp[N],pre[N],L[N],R[N];
vector<int>g[N];
vector<pair<int,pii>>vec;
bool check(int x){
for1(n){
L[i]=0;R[i]=m+1;
}
for(pair<int,pii> p:vec){
if(p.F>=vec.back().F-x)break;
L[p.S.F]=max(L[p.S.F],p.S.S);
}
for(int i=vec.size()-1;i>=0;i--){
pair<int,pii> p=vec[i];
if(p.F<=vec[0].F+x)break;
R[p.S.F]=min(R[p.S.F],p.S.S);
}
int mx=m;
bool o=1;
for1(n){
mx=min(mx,R[i]-1);
o&=(mx>=L[i]);
}
if(o)return 1;
int mn=0;
o=1;
for1(n){
mn=max(mn,L[i]+1);
o&=(R[i]>=mn);
}
if(o)return 1;
for1(n){
L[i]=0;R[i]=m+1;
}
for(pair<int,pii> p:vec){
if(p.F>=vec.back().F-x)break;
R[p.S.F]=min(R[p.S.F],p.S.S);
}
for(int i=vec.size()-1;i>=0;i--){
pair<int,pii> p=vec[i];
if(p.F<=vec[0].F+x)break;
L[p.S.F]=max(L[p.S.F],p.S.S);
}
mx=m;
o=1;
for1(n){
mx=min(mx,R[i]-1);
o&=(mx>=L[i]);
}
if(o)return 1;
mn=0;
o=1;
for1(n){
mn=max(mn,L[i]+1);
o&=(R[i]>=mn);
}
if(o)return 1;
return 0;
}
int main(){
fast_io
cin>>n>>m;
for1(n)for(int j=1;j<=m;j++){cin>>A[i][j];vec.pb({A[i][j],{i,j}});}
sort(all(vec));
int l=-1,r=mod;
while(r-l!=1){
int mid=(l+r)>>1;
if(check(mid)==0)l=mid;
else r=mid;
}
cout<<l+1<<endl;
}
