#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 2005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
ll tmn[5][MAX][MAX],tmx[5][MAX][MAX],n,a[MAX][MAX],m;
vll v;
map<ll,ll> mp;
ll OK(ll y,ll z){
if(y+1==v.size())return abs(v[0]-v.back());
ll x=v[y];
//cout<<x<<":";
ll cl=-1,mx=0,mn=oo;
for(int i=0;i<n;i++){
ll p=cl,f=m;
while(abs(p-f)!=1){
ll md=(p+f)/2;
if(tmn[0][i][md]<=x)p=md;
else f=md;
}
cl=p;
if(cl!=-1)mx=max(mx,tmx[1][i][cl]);
}//cout<<mx<<" ";
mn=min(mn,mx);cl=m,mx=0;
for(int i=0;i<n;i++){
ll p=-1,f=cl;
while(abs(p-f)!=1){
ll md=(p+f)/2;
if(tmn[1][i][md]>x)p=md;
else f=md;
}
cl=f;
if(cl!=-1)mx=max(mx,tmx[0][i][cl]);
}//cout<<mx<<" ";
mn=min(mn,mx);cl=-1,mx=0;
for(int i=n-1;i>=0;i--){
ll p=cl,f=m;
while(abs(p-f)!=1){
ll md=(p+f)/2;
if(tmn[0][i][md]<=x)p=md;
else f=md;
}
cl=p;
if(cl!=-1)mx=max(mx,tmx[1][i][cl]);
}//cout<<mx<<" ";
//cout<<"////////////////////////";
mn=min(mn,mx);cl=m,mx=0;
for(int i=n-1;i>=0;i--){
ll p=-1,f=cl;
while(abs(p-f)!=1){
ll md=(p+f)/2;///cout<<tmn[1][i][md]<<" "<<md<<"\n";
if(tmn[1][i][md]>x)p=md;
else f=md;
}
cl=f;//cout<<cl<<"-";
if(cl!=-1)mx=max(mx,tmx[0][i][cl]);
}//cout<<mx<<" ";
// cout<<"////////////////////////";
mn=min(mn,mx);
if(z==1)return max(abs(v[0]-mn),abs(v.back()-v[y+1]));
if(abs(v[0]-mn)<abs(v.back()-v[y+1]))return 1;
return 0;
}
int main(){
fast_in
cin>>n>>m;
for(int i=0;i<n;i++){
tmn[0][i][m]=tmn[1][i][0]=oo;
for(int j=0;j<m;j++){
cin>>a[i][j];
if(mp[a[i][j]]==0){
mp[a[i][j]]=1;
v.push_back(a[i][j]);
}
tmx[1][i][j]=max(tmx[1][i][j],a[i][j]);
tmx[1][i][j+1]=tmx[1][i][j];
tmn[1][i][j]=min(tmn[1][i][j],a[i][j]);
tmn[1][i][j+1]=tmn[1][i][j];
}
for(int j=m-1;j>=0;j--){
tmx[0][i][j]=max(tmx[0][i][j+1],a[i][j]);
tmn[0][i][j]=min(tmn[0][i][j+1],a[i][j]);
}
}
sort(v.begin(),v.end());
// for(auto i:v)cout<<i<<" ";cout<<"\n";
ll p=0,f=v.size();
while(abs(f-p)!=1){
ll md=(p+f)/2; // cout<<md;
if(OK(md,0)==1)p=md;
else f=md;
}
if(f==v.size()){cout<<0;return 0;}
// cout<<p<<" "<<f<<" ";
cout<<min(OK(p,1),OK(f,1));
return 0;
}
