#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
//#define int long long
const int nmax = 2e3 + 5;
const int lg = 18;
const int base = 311;
const int M = 5e6;
const ll oo = 1e9 + 1;
const int mod = 987654321;
#define fi first
#define se second
#define endl "\n"
#define debug(a, m) for(int j = 1; j <= n; ++j) cout << a[j] << ' ';cout << endl;
#define pii pair<ll, int>
using namespace std;
int n, m, a[nmax][nmax], mx = -1;
int pos[nmax], pre[nmax][nmax][2], suf[nmax][nmax][2];
int tmp[nmax][nmax];
bool check(int mid){
for(int k = 1; k <= 4; ++k){
for(int i = 1; i <= n; ++i){
pre[i][0][0] = suf[i][m + 1][0] = oo;
pre[i][0][1] = suf[i][m + 1][1] = -oo;
for(int j = 1; j <= m; ++j){
pre[i][j][0] = min(pre[i][j - 1][0], a[i][j]);
pre[i][j][1] = max(pre[i][j - 1][1], a[i][j]);
}
for(int j = m; j >= 1; --j){
suf[i][j][0] = min(suf[i][j + 1][0], a[i][j]);
suf[i][j][1] = max(suf[i][j + 1][1], a[i][j]);
}
}
for(int i = 1; i <= n; ++i){
pos[i] = -1;
for(int j = 1; j <= m; ++j){
if(mx - mid > a[i][j]){
pos[i] = j;
}
}
// cout << pos[i] << ' ';
}
// return 0;
int ma_1 = -oo, mi_1 = oo, ma_2 = -oo, mi_2 = oo, idx = 0;
for(int i = 1; i <= n; ++i){
idx = max(idx, pos[i]);
ma_1 = max(ma_1, pre[i][idx][1]);
ma_2 = max(ma_2, suf[i][idx + 1][1]);
mi_1 = min(mi_1, pre[i][idx][0]);
mi_2 = min(mi_2, suf[i][idx + 1][0]);
}
if(ma_1 - mi_1 <= mid && ma_2 - mi_2 <= mid) return 1;
ma_1 = -oo, mi_1 = oo, ma_2 = -oo, mi_2 = oo, idx = 0;
for(int i = n; i >= 1; --i){
idx = max(idx, pos[i]);
ma_1 = max(ma_1, pre[i][idx][1]);
ma_2 = max(ma_2, suf[i][idx + 1][1]);
mi_1 = min(mi_1, pre[i][idx][0]);
mi_2 = min(mi_2, suf[i][idx + 1][0]);
}
// cout <<ma_1 << ' ' <<mi_1 << ' ' << ma_2 << ' ' << mi_2 << ' ' << mi;
// return 0;
if(ma_1 - mi_1 <= mid && ma_2 - mi_2 <= mid) return 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
tmp[j][n - i + 1] = a[i][j];
}
}
swap(n, m);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
a[i][j] = tmp[i][j];
// cout << a[i][j] << ' ';
}
// cout << endl;
}
// return 0;
}
return 0;
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i<= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> a[i][j];
mx = max(mx, a[i][j]);
}
}
// vector<int> nen;
// for(int i = 1; i <= n; ++i){
// for(int j = 1; j <= m; ++j){
// nen.push_back(mx - a[i][j]);
// }
// }
// sort(nen.begin(), nen.end());
// nen.erase(unique(nen.begin(), nen.end()), nen.end());
// cout <<
//check(11);
int l = 1, r= 1e9, kq = -1;
while(l <= r){
int mid = r + l >> 1;
if(check(mid)){
kq = mid;
r = mid - 1;
}
else l= mid + 1;
}
cout << kq;
// cout << check(11);
// for(int i =1; i <= 100; ++i){
// cout << i << ' ' << check(i) << endl;
// }
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
*/
