#include<bits/stdc++.h>
using namespace std;
const int MX = 2005;
const int INF = 1e9;
int a[MX][MX];
int n, m;
int mn, mx;
int mark[MX][MX];
bool can(int ans, bool tag) {
for(int i=0; i<n; ++i) {
for(int j=0; j<m; ++j) {
mark[i][j] = -1;
if(a[i][j]-mn>ans) {
mark[i][j] = tag;
}
if(mx-a[i][j]>ans) {
if(mark[i][j]!=-1) return false;
mark[i][j] = tag^1;
}
}
}
auto LEFT_RIGHT_DIAGONAL = [&] () {
int prev = INF;
for(int i=0; i<n; ++i) {
int upto = m;
bool zero = false;
for(int j=m-1; j>-1; --j) {
if(mark[i][j]==0) {
zero = true;
if(j>prev) return false;
continue;
}
if(mark[i][j]==1) {
if(zero) return false;
upto = j;
}
}
prev = min(prev, upto-1);
}
return true;
};
auto RIGHT_LEFT_DIAGONAL = [&] () {
int prev = -1;
for(int i=0; i<n; ++i) {
int upto = -1;
bool one = false;
for(int j=0; j<m; ++j) {
if(mark[i][j]==1) {
one = true;
if(j<prev) return false;
continue;
}
if(mark[i][j]==0) {
if(one) return false;
upto = j;
}
}
prev = max(prev, upto+1);
}
return true;
};
return (LEFT_RIGHT_DIAGONAL()|(RIGHT_LEFT_DIAGONAL()));
}
void PlayGround() {
cin>>n>>m;
mx = -1, mn = INF;
for(int i=0; i<n; ++i) {
for(int j=0; j<m; ++j) {
cin>>a[i][j];
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
}
int l = 0, r = 1e9;
while(l<r) {
int mid = (l+r)/2;
if(can(mid, 0) || can(mid, 1)) r = mid;
else l = mid+1;
}
cout<<l<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
