#include<bits/stdc++.h>
using namespace std;
#define int long long
int r,c;
int a[2002][2002];
int mn=1e9,mx=0;
bool cek(int brp){
int posr=c;
bool ok=true,ok2=true;
for(int q=1;q<=r && ok;q++){
for(int w=1;w<=posr;w++){
if(a[q][w]>mn+brp){
posr=w-1; break;
}
}
for(int w=posr+1;w<=c;w++){
if(a[q][w]<mx-brp){
ok=false; break;
}
}
}
int posl=1;
for(int q=1;q<=r && ok2;q++){
for(int w=c;w>=posl;w--){
if(a[q][w]>mn+brp){
posl=w+1; break;
}
}
for(int w=posl-1;w>=1;w--){
if(a[q][w]<mx-brp){
ok2=false; break;
}
}
}
return (ok || ok2);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>r>>c;
for(int q=1;q<=r;q++){
for(int w=1;w<=c;w++){
cin>>a[q][w];
mx=max(mx,a[q][w]);
mn=min(mn,a[q][w]);
}
}
int ans=1e18;
int posl=0,posr=1e6;
while(posl<=posr){
int mid=(posl+posr)/2;
if(cek(mid)){
posr=mid-1;
ans=min(ans,mid);
}
else{
posl=mid+1;
}
}
for(int q=1;q<=r/2;q++){
for(int w=1;w<=c;w++){
swap(a[q][w],a[r+1-q][w]);
}
}
posl=0,posr=1e6;
while(posl<=posr){
int mid=(posl+posr)/2;
if(cek(mid)){
posr=mid-1;
ans=min(ans,mid);
}
else{
posl=mid+1;
}
}
cout<<ans<<endl;
}
