#include<bits/stdc++.h>
#define int long long
using namespace std;
int ar[2005][2005];
int mxpre[2005][2005],mnpre[2005][2005],mxsuf[2005][2005],mnsuf[2005][2005];
int h,w;
int inf=1e18;
pair<int,int> checkdec(int cut){
//cerr<<"\ncut:"<<cut<<"\n";
vector<int>l;
for(int i=1;i<=h;i++){
int id=upper_bound(mxpre[i]+1,mxpre[i]+w+1,cut)-mxpre[i]-1;
l.push_back(id);
}
int ans=0;
//dec
int c=w;
int lmx=0,lmn=inf,rmx=0,rmn=inf;
for(int i=1;i<=h;i++){
int temp=l[i-1];
c=min(c,temp);
lmx=max(lmx,mxpre[i][c]);
lmn=min(lmn,mnpre[i][c]);
rmx=max(rmx,mxsuf[i][c+1]);
rmn=min(rmn,mnsuf[i][c+1]);
}
ans=max(lmx-lmn,rmx-rmn);
return {lmx-lmn,rmx-rmn};
}
pair<int,int> checkinc(int cut){
vector<int>l;
for(int i=1;i<=h;i++){
int id=upper_bound(mxpre[i]+1,mxpre[i]+w+1,cut)-mxpre[i]-1;
l.push_back(id);
}
int ans=0;
int c=w;
int lmx=0,lmn=inf,rmx=0,rmn=inf;
for(int i=h;i>=1;i--){
int temp=l[i-1];
c=min(c,temp);
lmx=max(lmx,mxpre[i][c]);
lmn=min(lmn,mnpre[i][c]);
rmx=max(rmx,mxsuf[i][c+1]);
rmn=min(rmn,mnsuf[i][c+1]);
}
ans=max(lmx-lmn,rmx-rmn);
return {lmx-lmn,rmx-rmn};
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>h>>w;
vector<int>val;
for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)cin>>ar[i][j],val.push_back(ar[i][j]);
sort(val.begin(),val.end());
val.erase(unique(val.begin(),val.end()),val.end());
for(int i=0;i<=h+1;i++)for(int j=0;j<=w+1;j++)mxpre[i][j]=mxsuf[i][j]=0,mnpre[i][j]=mnsuf[i][j]=inf;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
mxpre[i][j]=max(mxpre[i][j-1],ar[i][j]);
mnpre[i][j]=min(mnpre[i][j-1],ar[i][j]);
}
for(int j=w;j>=1;j--){
mxsuf[i][j]=max(mxsuf[i][j+1],ar[i][j]);
mnsuf[i][j]=min(mnsuf[i][j+1],ar[i][j]);
}
}
int ans=inf;
for(int i=0;i<val.size();i++){
auto x=checkdec(val[i]);
ans=min(ans,max(x.first,x.second));
x=checkinc(val[i]);
ans=min(ans,max(x.first,x.second));
}
//rev
for(int i=1;i<=h;i++){
reverse(ar[i]+1,ar[i]+w+1);
}
for(int i=0;i<=h+1;i++)for(int j=0;j<=w+1;j++)mxpre[i][j]=mxsuf[i][j]=0,mnpre[i][j]=mnsuf[i][j]=inf;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
mxpre[i][j]=max(mxpre[i][j-1],ar[i][j]);
mnpre[i][j]=min(mnpre[i][j-1],ar[i][j]);
}
for(int j=w;j>=1;j--){
mxsuf[i][j]=max(mxsuf[i][j+1],ar[i][j]);
mnsuf[i][j]=min(mnsuf[i][j+1],ar[i][j]);
}
}
for(int i=0;i<val.size();i++){
auto x=checkdec(val[i]);
ans=min(ans,max(x.first,x.second));
x=checkinc(val[i]);
ans=min(ans,max(x.first,x.second));
}
cout<<ans;
}
