#include <bits/stdc++.h>
using namespace std;
int h,w,a[2006][2006],mn[2006][2],mx[2006][2],tmp[2006],lo=1e9,hi;
bool check(int x){
for (int i=1;i<=h;i++){
mx[i][0]=mx[i][1]=-1;
mn[i][0]=mn[i][1]=1e9;
for (int j=1;j<=w;j++){
if (a[i][j]>lo+x&&a[i][j]<hi-x)
return false;
if (a[i][j]>=hi-x&&a[i][j]<=lo+x)
continue;
int val=(a[i][j]>=hi-x);
mx[i][val]=max(mx[i][val],j);
mn[i][val]=min(mn[i][val],j);
}
}
int ch=4;
tmp[h+1]=0;
for (int k=0;k<2;k++){
for (int i=1;i<=h;i++)
tmp[i]=max(tmp[i-1],mx[i][k]);
int cur=w+1;
for (int i=h;i>=1;i--){
cur=min(cur,mn[i][k^1]);
if (cur<=tmp[i]){
ch--;
break;
}
}
for (int i=h;i>=1;i--)
tmp[i]=max(tmp[i+1],mx[i][k]);
cur=w+1;
for (int i=1;i<=h;i++){
cur=min(cur,mn[i][k^1]);
if (cur<=tmp[i]){
ch--;
break;
}
}
}
return ch;
}
int main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> h >> w;
for (int i=1;i<=h;i++)
for (int j=1;j<=w;j++){
cin >> a[i][j];
lo=min(lo,a[i][j]);
hi=max(hi,a[i][j]);
}
int l=0,r=1e9,kq=-1;
while (l<=r){
int mid=(l+r)>>1;
if (check(mid)){
kq=mid;
r=mid-1;
}
else
l=mid+1;
}
cout << kq;
}
