#include<bits/stdc++.h>
using namespace std;
//#define int long long
int n;int m;
int TPV;int BTV;
int gr[2010][2010];
int tgr[2010][2010];
int psmx[2010][2010];
int psmn[2010][2010];
int sfmx[2010][2010];
int sfmn[2010][2010];
int ans;
int chmx(int id,int l,int r){
if(l==1){
return psmx[id][r];
}
return sfmx[id][l];
}
int chmn(int id,int l,int r){
if(l==1){
return psmn[id][r];
}
return sfmn[id][l];
}
void spin(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
tgr[j][n-i+1 ]=gr[i][j];
}
}
swap(n,m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
gr[i][j]=tgr[i][j];
}
}
}
void precalc(){
for(int i=1;i<=n;i++){
psmn[i][1]=gr[i][1];
psmx[i][1]=gr[i][1];
for(int j=2;j<=m;j++){
psmn[i][j]=min(psmn[i][j-1],gr[i][j]);
psmx[i][j]=max(psmx[i][j-1],gr[i][j]);
}
sfmn[i][m]=gr[i][m];
sfmx[i][m]=gr[i][m];
for(int j=m-1;j>=1;j--){
sfmn[i][j]=min(sfmn[i][j+1],gr[i][j]);
sfmx[i][j]=max(sfmx[i][j+1],gr[i][j]);
}
}
}
int ok1(int mid){
int lst=m;
int tp=TPV-mid;
int bt=BTV+mid;
for(int i=1;i<=n;i++){
int l=0;int r=lst;
while(l<r){
int mi=l+(r-l+1)/2;
if((mi==0||(mi!=0&&chmn(i,1,mi)>=tp)) ){
l=mi;
}else{
r=mi-1;
}
}
lst=l;
if((lst!=m&&chmx(i,lst+1,m)>bt) ){return 0;}
}
return 1;
}
int ok2(int mid){
int lst=m;
int tp=TPV-mid;
int bt=BTV+mid;
for(int i=1;i<=n;i++){
int l=0;int r=lst;
while(l<r){
int mi=l+(r-l+1)/2;
if((mi==0||(mi!=0&&chmx(i,1,mi)<=bt)) ){
l=mi;
}else{
r=mi-1;
}
}
lst=l;
if((lst!=m&&chmn(i,lst+1,m)<tp) ){return 0;}
}
return 1;
}
int solve(){
int l=0;int r=1e9;
while(l<r){
int mi=l+(r-l)/2;
if((ok1(mi)||ok2(mi))){
r=mi;
}else{
l=mi+1;
}
}
return l;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>gr[i][j];
}
}
TPV=gr[1][1];BTV=gr[1][1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
TPV=max(TPV,gr[i][j]);
BTV=min(BTV,gr[i][j]);
}
}
ans=1e9;
precalc();
ans=solve();
for(int t=1;t<=3;t++){
spin();
precalc();
ans=min(ans,solve());
}
cout<<ans<<endl;
}
