#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e3 + 5;
int pre[maxn][maxn][2], suf[maxn][maxn][2], a[maxn][maxn];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
int mn = 1e9, mx = -1e9;
for(int i = 1; i <= n; i++){
pre[i][0][0] = suf[i][m + 1][0] = 1e9;
pre[i][0][1] = suf[i][m + 1][1] = -1e9;
for(int j = 1; j <= m; j++){
cin >> a[i][j];
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
pre[i][j][0] = min(a[i][j], pre[i][j - 1][0]);
pre[i][j][1] = max(a[i][j], pre[i][j - 1][1]);
}
for(int j = m; j >= 1; j--){
suf[i][j][0] = min(a[i][j], suf[i][j + 1][0]);
suf[i][j][1] = max(a[i][j], suf[i][j + 1][1]);
}
}
auto ok = [&](int mid){
int j1 = m, j2 = m , j3 = m, j4 = m, v1 = 1, v2 = 1, v3 = 1, v4 = 1;
for(int i = 1; i <= n; i++){
while(j1 && mx - pre[i][j1][0] > mid) j1--;
v1 &= (suf[i][j1 + 1][1] - mn <= mid);
while(j2 && pre[i][j2][1] - mn > mid) j2--;
v2 &= (mx - suf[i][j2 + 1][0] <= mid);
}
for(int i = n; i >= 1; i--){
while(j3 && mx - pre[i][j3][0] > mid) j3--;
v3 &= (suf[i][j3 + 1][1] - mn <= mid);
while(j4 && pre[i][j4][1] - mn > mid) j4--;
v4 &= (mx - suf[i][j4 + 1][0] <= mid);
}
return v1 | v2 | v3 | v4;
};
int l = 0, r = mx - mn, res = mx - mn;
while(l <= r){
int mid = (l + r) / 2;
if(ok(mid)) res = mid, r = mid - 1;
else l = mid + 1;
}
cout << res;
}
