#include<bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>
using vvector = vector<vector<T>>;
const int INF = 0x3f3f3f3f;
bool ok(int h,int w,vvector<ll> &a,int mn,int mx,ll x) {
vector<pll> rg1(h+1,{INF,0}),rg2(h+1,{INF,0});
int d=-1;
for (int i=1;i<=h;i++) {
for (ll j=1;j<=w;j++) {
if (a[i][j]>mn+x) {
rg2[i].F=min(j,rg2[i].F);
rg2[i].S=max(j,rg2[i].S);
}
if (a[i][j]<mx-x) {
rg1[i].F=min(j,rg1[i].F);
rg1[i].S=max(j,rg1[i].S);
}
}
if (!(rg1[i].S<rg2[i].F or rg2[i].S<rg1[i].F)) return false;
if (d==-1) d=rg1[i].S<rg2[i].F;
else {
if (d!=rg1[i].S<rg2[i].F) return false;
}
}
// cout<<x<<" x\n";
// for (int i=1;i<=h;i++) {
// cout<<rg1[i].F<<" "<<rg1[i].S<<"\n";
// }
// cout<<"\n";
// for (int i=1;i<=h;i++) {
// cout<<rg1[i].F<<" "<<rg1[i].S<<"\n";
// }
// cout<<"--------------\n";
bool flagd=true;
ll now=w;
for (int i=1;i<=h;i++) {
if (d) {
now=min(now,rg1[i].S);
if (now<rg1[i].F) {
flagd=false;
break;
}
} else {
now=min(now,rg2[i].S);
if (now<rg2[i].F) {
flagd=false;
break;
}
}
}
bool flaga=true;
now=0;
for (int i=1;i<=h;i++) {
if (d) {
now=max(now,rg1[i].F);
if (rg1[i].S<now) {
flagd=false;
break;
}
} else {
now=max(now,rg2[i].F);
if (rg2[i].S<now) {
flagd=false;
break;
}
}
}
return flaga or flagd;
}
int main() {
speed;
ll h,w;
cin>>h>>w;
vvector<ll> a(h+1,vector<ll>(w+1));
ll mn=INF,mx=0;
for (int i=1;i<=h;i++) {
for (int j=1;j<=w;j++) {
cin>>a[i][j];
mx=max(mx,a[i][j]);
mn=min(mn,a[i][j]);
}
}
ll l=0,r=INF;
while (l<r) {
int mid=l+r>>1;
if (ok(h,w,a,mn,mx,mid)) r=mid;
else l=mid+1;
}
cout<<l<<"\n";
return 0;
}
