#include <bits/stdc++.h>
using namespace std;
const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 2002
ii n, m, a;
pair<ii,ii> p[maxn];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
//freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
cin >> n >> m;
ii mn = INFii;
ii mx = 0;
priority_queue<pair<ii,pair<ii,ii>>> val;
for(ii i = 1; i <= n; i++) {
for(ii j = 1; j <= m; j++) {
cin >> a;
val.push(mp(a,mp(i,j)));
mn = min(mn,a);
mx = max(mx,a);
}
}
if(mn == mx) {
cout << 0 << endl;
return 0;
}
vector<pair<pair<ii,ii>,vector<pair<ii,ii>>>> pq;
vector<pair<ii,ii>> vazio;
ii ant = -1;
while(val.size()) {
if(val.top().fr != ant) {
ant = val.top().fr;
pq.pb(mp(mp(val.top().fr-mn,0),vazio));
pq.pb(mp(mp(mx-val.top().fr,1),vazio));
}
else {
pq[pq.size()-1].sc.pb(val.top().sc);
pq[pq.size()-2].sc.pb(val.top().sc);
val.pop();
}
}
sort(all(pq), greater<pair<pair<ii,ii>,vector<pair<ii,ii>>>>());
// com minimo na esquerda:
ii l = 0;
ii r = 1e9+1;
ii ans1;
while(l <= r) {
for(ii i = 1; i <= n; i++) {
p[i].fr = 0;
p[i].sc = m+1;
}
for(ii i = 0; i < pq.size() && pq[i].fr.fr >= (l+r)/2; i++) {
for(auto x : pq[i].sc) {
if(pq[i].fr.sc == 1) { // tem que ta junto com o mn
p[x.fr].fr = max(p[x.fr].fr,x.sc);
}
else {
p[x.fr].sc = min(p[x.fr].sc,x.sc-1);
}
}
}
//ver se ta crescente/decrescente
ii actc = 0; bool okc = 1;
ii actd = m+1; bool okd = 1;
for(ii i = 1; i <= n; i++) {
actc = max(actc,p[i].fr);
if(actc > p[i].sc || p[i].fr > p[i].sc) okc = 0;
actd = min(actd,p[i].sc);
if(actd < p[i].fr || p[i].fr > p[i].sc) okd = 0;
}
if(okc || okd) {
//se deu bom com esse (l+r)/2 quero abaixar o (l+r)/2
ans1 = (l+r)/2-1;
r = (l+r)/2-1;
}
else {
l = (l+r)/2+1;
}
}
//com mx na esquerda
for(ii i = 0; i < pq.size(); i++) {
pq[i].fr.sc^= 1;
}
l = 0;
r = 1e9+1;
ii ans2;
while(l <= r) {
for(ii i = 1; i <= n; i++) {
p[i].fr = 0;
p[i].sc = m+1;
}
for(ii i = 0; i < pq.size() && pq[i].fr.fr >= (l+r)/2; i++) {
for(auto x : pq[i].sc) {
if(pq[i].fr.sc == 1) { // tem que ta junto com o mn
p[x.fr].fr = max(p[x.fr].fr,x.sc);
}
else {
p[x.fr].sc = min(p[x.fr].sc,x.sc-1);
}
}
}
//ver se ta crescente/decrescente
ii actc = 0; bool okc = 1;
ii actd = m+1; bool okd = 1;
for(ii i = 1; i <= n; i++) {
actc = max(actc,p[i].fr);
if(actc > p[i].sc || p[i].fr > p[i].sc) okc = 0;
actd = min(actd,p[i].sc);
if(actd < p[i].fr || p[i].fr > p[i].sc) okd = 0;
}
if(okc || okd) {
//se deu bom com esse (l+r)/2 quero abaixar o (l+r)/2
ans2 = (l+r)/2-1;
r = (l+r)/2-1;
}
else {
l = (l+r)/2+1;
}
}
cout << min(ans1,ans2) << endl;
}
