#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e3+7, INF=1e9+7;
int A[LIM][LIM], T[LIM][LIM], n, m;
bool f(int x) {
int ma=0, mi=INF;
rep(i, n) rep(j, m) {
ma=max(ma, A[i][j]);
mi=min(mi, A[i][j]);
}
rep(i, n) rep(j, m) {
T[i][j]=0;
if(A[i][j]-mi<=x) ++T[i][j];
if(ma-A[i][j]<=x) T[i][j]+=2;
if(!T[i][j]) return false;
}
bool ok=true;
int lst=m;
rep(i, n) {
int akt=0;
while(akt<lst && T[i][akt]!=1) ++akt;
lst=akt;
for(int j=m-1; j>=akt; --j) if(T[i][j]==2) ok=false;
}
if(ok) return true;
ok=true;
lst=m;
rep(i, n) {
int akt=0;
while(akt<lst && T[i][akt]!=2) ++akt;
lst=akt;
for(int j=m-1; j>=akt; --j) if(T[i][j]==1) ok=false;
}
if(ok) return true;
ok=true;
lst=-1;
rep(i, n) {
int akt=m-1;
while(akt>lst && T[i][akt]!=1) --akt;
lst=akt;
for(int j=akt; j>=0; --j) if(T[i][j]==2) ok=false;
}
if(ok) return true;
ok=true;
lst=-1;
rep(i, n) {
int akt=m-1;
while(akt>lst && T[i][akt]!=2) --akt;
lst=akt;
for(int j=akt; j>=0; --j) if(T[i][j]==1) ok=false;
}
return ok;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
rep(i, n) rep(j, m) cin >> A[i][j];
int p=0, k=INF;
while(p<k) {
int sr=(p+k)/2;
if(f(sr)) k=sr; else p=sr+1;
}
cout << p << '\n';
}
