#include <bits/stdc++.h>
using namespace std;
#undef wambule
#define wambule
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
#include ".h"
#else
#endif
const int N = 2003, M = N;
int n, m, a[N][M], ox, on = 1e9, z;
void X() {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m / 2; ++j) {
swap(a[i][j], a[i][m - 1 - j]);
}
}
}
void Y() {
for(int i = 0; i < n / 2; ++i) {
for(int j = 0; j < m; ++j) {
swap(a[i][j], a[n - 1 - i][j]);
}
}
}
bool C(int x) {
int y = m;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < y; ++j) {
if(ox - x > a[i][j]) {
y = j;
break;
}
}
for(int j = y; j < m; ++j) {
if(on + x < a[i][j]) {
return 0;
}
}
}
return 1;
}
int D() {
int l = 0, r = ox - on;
while(l < r) {
int m = (l + r) / 2;
// cout << m << " " << C(m) << endl;
if(m == 7) ++z;
if(C(m)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
#ifdef wambule
mt19937 rnd(time(0));
int R(int l, int r) {
return 1ll * rnd() % (r - l + 1) + l;
}
const int inf = 1e9 + 1;
int ffp;
void G(int i, int y, int lx = 0, int ln = inf, int rx = 0, int rn = inf) {
if(i == n) {
if(ln == inf || rn == inf) return;
ffp = min(ffp, max(lx - ln, rx - rn));
return;
}
for(int j = -1; j < y; ++j) {
int nln = inf, nlx = 0, nrn = inf, nrx = 0;
for(int jj = 0; jj <= j; ++jj) {
nln = min(nln, a[i][jj]);
nlx = max(nlx, a[i][jj]);
}
for(int jj = j + 1; jj < m; ++jj) {
nrn = min(nrn, a[i][jj]);
nrx = max(nrx, a[i][jj]);
}
G(i + 1, j + 1, max(nlx, lx), min(nln, ln), max(nrx, rx), min(nrn, rn));
}
}
int V() {
ffp = inf;
G(0, m);
Y();
G(0, m);
X();
G(0, m);
Y();
G(0, m);
X();
return ffp;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int rtg = 1;
if(rtg == 1) {
cin >> n >> m;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
cin >> a[i][j];
ox = max(ox, a[i][j]);
on = min(on, a[i][j]);
}
}
int fp = D();
Y();
fp = min(fp, D());
X();
fp = min(fp, D());
Y();
fp = min(fp, D());
cout << fp << endl;
} else if(rtg == 2) {
n = m = 4;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
a[i][j] = R(0, 9);
ox = max(ox, a[i][j]);
on = min(on, a[i][j]);
}
}
int fp = D();
Y();
fp = min(fp, D());
X();
fp = min(fp, D());
Y();
fp = min(fp, D());
X();
V();
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
cout << a[i][j] << " ";
}
cout << endl;
}
cout << fp << " " << ffp << endl;
}
return 0;
}
#endif
