#include <bits/stdc++.h>
using namespace std;
int const MAX=4e6+5;
struct block{
int l,c,val;
bool operator<(block ot){
return val<ot.val;
}
}blocks[MAX];
int n,m;
int minim[MAX],maxim[MAX];
void read(){
cin>>n>>m;
int i,j;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j){
int val;
cin>>val;
blocks[(i-1)*m+j]={i,j,val};
}
sort(blocks+1,blocks+n*m+1);
}
void minself(int& x,int val){
if(x>val)
x=val;
}
void maxself(int& x,int val){
if(x<val)
x=val;
}
bool check_matrix(int l1,int r1,int l2,int r2){
int i;
for(i=1;i<=n;++i){
minim[i]=m+1;
maxim[i]=0;
}
for(i=l1;i<=r1;++i){
auto [l,c,val]=blocks[i];
maxself(maxim[l],c);
}
for(i=l2;i<=r2;++i){
auto [l,c,val]=blocks[i];
minself(minim[l],c);
}
for(i=1;i<=n;++i)
if(maxim[i]>minim[i])
return 0;
int mxm=0;
for(i=1;i<=n;++i){
maxself(mxm,maxim[i]);
if(mxm>=minim[i])
break;
}
if(i==n+1)
return 1;
mxm=0;
for(i=n;i;--i){
maxself(mxm,maxim[i]);
if(mxm>=minim[i])
break;
}
if(i==0)
return 1;
return 0;
}
bool check(int val){
int i;
for(i=1;i<=n*m;++i)
if(blocks[i].val-blocks[1].val>val && blocks[n*m].val-blocks[i].val>val)
return 0;
int st=1,dr=n*m;
/// (]
while(dr-st>1){
int mij=(st+dr)/2;
if(blocks[mij].val-blocks[1].val>val)
dr=mij;
else
st=mij;
}
int id2=dr;
st=1,dr=n*m;
/// [)
while(dr-st>1){
int mij=(st+dr)/2;
if(blocks[n*m].val-blocks[mij].val>val)
st=mij;
else
dr=mij;
}
int id1=st;
if(check_matrix(1,id1,id2,n*m))
return 1;
if(check_matrix(id2,n*m,1,id1))
return 1;
return 0;
}
int bin_search(){
/// (]
int st=-1,dr=blocks[n*m].val-blocks[1].val;
while(dr-st>1){
int mij=(st+dr)/2;
if(check(mij))
dr=mij;
else
st=mij;
}
return dr;
}
int main()
{
read();
cout<<bin_search();
return 0;
}
