//fast
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(n) for(int i = 0 ; i<n ; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
const int base = 2e3+7;
int a[base][base];
int n,m;
int mini,maks;
void flipx(){
rep(n){
for (int j = 0 ; j<m/2 ; j++){
swap(a[i][j],a[i][m-j-1]);
}
}
}
void flipy(){
for (int j = 0 ; j<m ; j++){
rep(n/2){
swap(a[i][j],a[n-i-1][j]);
}
}
}
bool dasie(int x){
int last = m;
int xd = 0;
rep(n){
int c = 0;
for (int j = 0 ; j<m ; j++){
if (a[i][j]<maks-x){
c = j;
break;
}else c = j+1;
}
for (int j = min(c,last) ; j<m ; j++){
xd = max(xd,a[i][j]);
}
last = min(c,last);
}
if (xd-mini<=x) return 1;
return 0;
}
int wyn(){
int p = -1;
int k = 1e9;
while (k-p>1){
int s = (k+p)/2;
if (dasie(s)) k = s;
else p = s;
}
return k;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
mini = 1e9+7;
rep(n){
for (int j = 0 ; j<m ; j++){
cin >> a[i][j];
mini = min(mini,a[i][j]);
maks = max(maks,a[i][j]);
}
}
int w = 1e9+7;
w = min(w,wyn());
flipx();
w = min(w,wyn());
flipy();
w = min(w,wyn());
flipx();
w = min(w,wyn());
cout << w << '\n';
return 0;
}
