#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define mset(a,v) memset(a,v,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define forn(i,a,b) for(int i = a; i<b; i++)
#ifdef D
#define debug(x) cout<<x
#else
#define debug(x) //nada
#endif
using namespace std;
typedef long long ll;
const int MAXN = 2000+5;
const int MAXM = 2000+5;
ll grid[MAXN][MAXM][5];
ll n,m;
bool puede(ll ind, ll a, ll b ,ll &last){
// [-inf,a] n [b , inf] = nulo => return true
vector<ll> vals;
forn(j,0,m){
ll minimo = 1000000000000000;
if(SZ(vals)>=1) minimo=min(minimo,vals.back());
forn(i,0,n){
if(grid[i][j][ind]<=a){
minimo=min(minimo,(ll)i);
break;
}
}
vals.pb(minimo);
}
ll mini = 1000000000;
ll maxi = 0;
forn(j,0,m){
for(int i = n-1; i>=0; i--){
if(grid[i][j][ind]>=b){
if(i>=vals[j]) return false;
break;
}
}
}
ll mini0=1000000000;
ll maxi0=0;
ll mini1=1000000000;
ll maxi1=0;
forn(i,0,n){
forn(j,0,m){
if(i<vals[j]) mini0=min(mini0,grid[i][j][ind]),maxi0=max(maxi0,grid[i][j][ind]);
else mini1=min(mini1,grid[i][j][ind]),maxi1=max(maxi1,grid[i][j][ind]);
}
}
debug(maxi0<<" "<<mini0<<" "<<maxi1<<" "<<mini1<<'\n');
last=max(maxi0-mini0,maxi1-mini1);
return true;
}
int main(){
vector<ll> vals;
cin>>n>>m;
forn(i,0,n){
forn(j,0,m){
cin>>grid[i][j][0];
vals.pb(grid[i][j][0]);
}
}
forn(i,0,n){
forn(j,0,m){
grid[i][m-j-1][1]=grid[i][j][0];
grid[n-i-1][j][2]=grid[i][j][0];
grid[n-i-1][m-j-1][3]=grid[i][j][0];
}
}
sort(ALL(vals));
vals.erase(unique(ALL(vals)),vals.end());
ll lastaa=vals.back()-vals[0];
ll l = vals[0]; ll r=vals.back()-(vals.back()-vals[0]+1)/2;
while(l<=r){
ll i = (l+r)/2;
debug(i<<"] -- ["<<vals.back()-((i-vals[0]))<<'\n');
bool yes=false;
ll lasta=0;
ll last=100000000000;
forn(k,0,4){
if(puede(k,i,vals.back()-((i-vals[0])),lasta)) yes=true,last=min(last,lasta);
}
if(yes){lastaa=last;
debug(last<<'\n');
}
if(!yes){
r=i-1;
}else{
l=i+1;
}
}
ll lasta;
ll last=vals.back()-vals[0];
forn(k,0,4){
if(puede(k,r,vals.back()-((r-vals[0])),lasta))last=min(last,lasta);
}
cout<<last<<'\n';
return 0;
}
