#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <numeric>
#include <random>
#include <ratio>
#include <sstream>
#include <utility>
#include <bitset>
#include <deque>
#include <queue>
#include <map>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <string>
#include <set>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
llo n,m;
llo it[2001][2001];
llo mi=1000000001;
llo ma=0;
llo check(){
llo low=0;
llo high=ma-1;
while(low<high){
llo mid=(low+high)/2;
llo st=1;
llo ll=0;
for(llo i=0;i<n;i++){
for(llo j=0;j<m;j++){
if(it[i][j]<ma-mid){
ll=max(ll,j+1);
}
}
for(llo j=0;j<ll;j++){
if(it[i][j]>mi+mid){
st=0;
}
}
}
if(st){
high=mid;
}
else{
low=mid+1;
}
}
return low;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(llo i=0;i<n;i++){
for(llo j=0;j<m;j++){
cin>>it[i][j];
ma=max(ma,it[i][j]);
mi=min(mi,it[i][j]);
}
}
llo ans=check();
for(llo i=0;i<n;i++){
for(llo j=0;j<m/2;j++){
swap(it[i][j],it[i][m-j-1]);
}
}
ans=min(ans,check());
for(llo i=0;i<n/2;i++){
for(llo j=0;j<m;j++){
swap(it[i][j],it[n-i-1][j]);
}
}
ans=min(ans,check());
for(llo i=0;i<n;i++){
for(llo j=0;j<m/2;j++){
swap(it[i][j],it[i][m-j-1]);
}
}
ans=min(ans,check());
cout<<ans<<endl;
return 0;
}
