#include <bits/stdc++.h>
#define DIMN 2010
using namespace std;
int mini , maxi , n , m , sol;
int a[DIMN][DIMN] , where[DIMN][DIMN] , h[DIMN];
priority_queue <pair <int , pair <int,int> > > up , down;
char buff[DIMN * DIMN * 12];
int pos;
int getnr(){
int nr = 0;
while ('0' > buff[pos] || buff[pos] > '9')
pos++;
while ('0' <= buff[pos] && buff[pos] <= '9'){
nr = nr * 10 + buff[pos] - '0';
pos++;
}
return nr;
}
void solve(){
int i , j , maxis , minis , maxij , minij , val , ic , jc;
/// jos includ mini, sus includ maxi
for (i = 1 ; i <= n ; ++i)
memset (where[i] , 0 , sizeof(where[i]));
for (j = 1 ; j <= m ; ++j){
for (i = 1 ; i <= n ; ++i){
if (a[i][j] == mini)
break;
}
h[j] = max(n - i + 1 , h[j - 1]); /// fie iau exact cat trb fie mai mult
for (i = 1 ; i <= h[j] ; ++i)
where[n - i + 1][j] = 1; /// apartine tarii de jos
}
minij = minis = 2000000000;
maxij = maxis = -2000000000;
/// e clar ca toate mini urile sunt jos
for (i = 1 ; i <= n ; ++i){
for (j = 1 ; j <= m ; ++j){
if (where[i][j] == 0){
minis = min (minis , a[i][j]);
maxis = max (maxis , a[i][j]);
}
else {
minij = min (minij , a[i][j]);
maxij = max (maxij , a[i][j]);
}
}
}
/// daca exista vreun maxi jos, nu e ok
if (maxij == maxi)
return;
/// altfel, toate mini urile sunt jos, toate maxi urile sunt sus
while (!down.empty())
down.pop();
while (!up.empty())
up.pop();
for (j = 1 ; j <= m ; ++j){
if (j == m || h[j] < h[j + 1])
down.push( make_pair( -a[n - h[j]][j] , make_pair(n - h[j] , j)) );
}
/// in down pui candidatii
for (i = 1 ; i <= n ; ++i){
for (j = 1 ; j <= m ; ++j){
if (where[i][j] == 0){
up.push( make_pair( -a[i][j] , make_pair(i , j)) );
}
}
}
while (!down.empty()){
val = -down.top().first;
ic = down.top().second.first;
jc = down.top().second.second;
down.pop();
/// val = cea mai mica val cu care pot sa extind
maxij = max(maxij , val);
if (maxij == maxi)
return;
where[ic][jc] = 1;
h[jc]++;
if (h[jc - 1] + 1 == h[jc] && jc - 1 != 0 && n - h[jc - 1] > 0)
down.push( make_pair( -a[n - h[jc - 1]][jc - 1] , make_pair(n - h[jc - 1] , jc - 1)) );
if ((jc == m || h[jc] != h[jc + 1]) && n - h[jc] > 0)
down.push( make_pair( -a[n - h[jc]][jc] , make_pair(n - h[jc] , jc)) );
val = -up.top().first;
minis = val;
ic = up.top().second.first;
jc = up.top().second.second;
while (where[ic][jc]){
up.pop();
if (up.empty())
break;
val = -up.top().first;
ic = up.top().second.first;
jc = up.top().second.second;
minis = val;
}
if (!up.empty())
sol = min(sol , max(maxis - minis , maxij - minij));
else break;
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int i , j , st , dr;
fread(buff , 1 , DIMN * DIMN * 12 , fin);
n = getnr();
m = getnr();
mini = 2000000000;
maxi = -2000000000;
for (i = 1 ; i <= n ; i++){
for (j = 1 ; j <= m ; j++){
a[i][j] = getnr();
mini = min(mini , a[i][j]);
maxi = max(maxi , a[i][j]);
}
}
sol = maxi - mini;
solve();
for (i = 1 ; i <= n ; i++){
st = 1;
dr = m;
while (st < dr){
swap(a[i][st] , a[i][dr]);
st++;
dr--;
}
}
solve();
for (j = 1 ; j <= m ; j++){
st = 1;
dr = n;
while (st < dr){
swap(a[st][j] , a[dr][j]);
st++;
dr--;
}
}
solve();
for (i = 1 ; i <= n ; i++){
st = 1;
dr = m;
while (st < dr){
swap(a[i][st] , a[i][dr]);
st++;
dr--;
}
}
solve();
fprintf (fout,"%d",sol);
return 0;
}
