#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){
ll x=v[y],cl=-1,mx=0,mn=oo;
for(int i=0;i<n;i++){
while(cl!=m && tmn[0][i][cl+1]<x)cl++;
if(cl!=-1)mx=max(mx,tmx[1][i][cl]);
}
mn=min(mn,mx);cl=m;mx=0;
for(int i=0;i<n;i++){
while(cl-1>=0 && tmn[1][i][cl-1]<x)cl--;
if(cl!=-1)mx=max(mx,tmx[0][i][cl]);
}
mn=min(mn,mx);cl=-1;mx=0;
for(int i=n-1;i>=0;i--){
while(cl!=m && tmn[0][i][cl+1]<x)cl++;
if(cl!=-1)mx=max(mx,tmx[1][i][cl]);
}
mn=min(mn,mx);cl=m;mx=0;
for(int i=n-1;i>=0;i--){
while(cl-1>=0 && tmn[1][i][cl-1]<x)cl--;
if(cl!=-1)mx=max(mx,tmx[0][i][cl]);
}
mn=min(mn,mx);
if(z==1)return max(abs(v[0]-mn),abs(v.back()-v[y]));
if(abs(v[0]-mn)<=abs(v.back()-v[y]))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());
ll p=-1,f=v.size();
while(abs(f-p)!=1){
ll md=(p+f)/2;
if(OK(md,0)==1)p=md;
else f=md;
}
if(f==v.size()){cout<<OK(p,1);return 0;}
cout<<min(OK(p,1),OK(f,1));
return 0;
}
