#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 2e3 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll BASE = 137;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m;
int mn;
int a[N][N];
bool dd[N][N], dd2[N][N];
bool prec[N][N], sufc[N][N];
bool check (int X) {
rep (i, 1, n)
rep (j, 1, m) dd[i][j] = 0;
static queue<pair<int,int>> Q;
rep (i, 1, n)
rep (j, 1, m) if (a[i][j] == mn) Q.push({i, j});
while (!Q.empty()) {
pair<int,int> u = Q.front();
Q.pop();
rep (k, 0, 3) {
int ni = u.fs + dx[k], nj = u.se + dy[k];
if (ni >= 1 && ni <= n && nj >= 1 && nj <= m && dd[ni][nj] == 0 && a[ni][nj] <= mn + X) {
dd[ni][nj] = 1;
Q.push({ni, nj});
}
}
}
{
rep (i, 1, n)
rep (j, 1, m) dd2[i][j] = 0;
int mnR = n;
rep (j, 1, m) {
rep (i, 1, mnR) {
if (dd[i][j] == 0) {
mnR = i - 1;
break;
}
else dd2[i][j] = 1;
}
}
// rep (i, 1, n)
// rep (j, 1, m) cout << dd2[i][j] <<" \n"[j == m];
int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
rep (i, 1, n) rep (j, 1, m) if (dd2[i][j]) {
mn1 = min(mn1, a[i][j]);
mx1 = max(mx1, a[i][j]);
}
else {
mx2 = max(mx2, a[i][j]);
mn2 = min(mn2, a[i][j]);
}
// cout << max(mx2 - mn2, mx1 - mn1) <<"\n";
if (max(mx2 - mn2, mx1 - mn1) <= X) {
return 1;
}
}
{
rep (i, 1, n)
rep (j, 1, m) dd2[i][j] = 0;
int mnR = 1;
reb (j, m, 1) {
reb (i, n, mnR) {
if (dd[i][j] == 0) {
mnR = i + 1;
break;
}
else dd2[i][j] = 1;
}
}
int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
rep (i, 1, n) rep (j, 1, m) if (dd2[i][j]) {
mn1 = min(mn1, a[i][j]);
mx1 = max(mx1, a[i][j]);
}
else {
mx2 = max(mx2, a[i][j]);
mn2 = min(mn2, a[i][j]);
}
// cout << mx2 <<" "<<mn2 <<"\n";
if (max(mx2 - mn2, mx1 - mn1) <= X) return 1;
}
{
rep (i, 1, n)
rep (j, 1, m) dd2[i][j] = 0;
int mnR = n;
reb (j, m, 1) {
rep (i, 1, mnR) {
if (dd[i][j] == 0) {
mnR = i - 1;
break;
}
else dd2[i][j] = 1;
}
}
int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
rep (i, 1, n) rep (j, 1, m) if (dd2[i][j]) {
mn1 = min(mn1, a[i][j]);
mx1 = max(mx1, a[i][j]);
}
else {
mx2 = max(mx2, a[i][j]);
mn2 = min(mn2, a[i][j]);
}
// cout << mx2 <<" "<<mn2 <<"\n";
if (max(mx2 - mn2, mx1 - mn1) <= X) return 1;
}
{
rep (i, 1, n)
rep (j, 1, m) dd2[i][j] = 0;
int mnR = 1;
rep (j, 1, m) {
reb(i, n, mnR) {
if (dd[i][j] == 0) {
mnR = i + 1;
break;
}
else dd2[i][j] = 1;
}
}
int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
rep (i, 1, n) rep (j, 1, m) if (dd2[i][j]) {
mn1 = min(mn1, a[i][j]);
mx1 = max(mx1, a[i][j]);
}
else {
mx2 = max(mx2, a[i][j]);
mn2 = min(mn2, a[i][j]);
}
// cout << mx2 <<" "<<mn2 <<"\n";
if (max(mx2 - mn2, mx1 - mn1) <= X) return 1;
}
return 0;
}
void solution () {
cin >> n >> m;
rep (i, 1, n)
rep (j, 1, m)
cin >> a[i][j];
mn = INF;
rep (i, 1, n)
rep (j, 1, m) {
if (a[i][j] < mn) mn = a[i][j];
}
// cout << check(18) <<"\n";
// return;
int lf = 0, rt = 1e9;
while (lf < rt) {
int mid = lf + rt >> 1;
if (check(mid)) rt = mid;
else lf = mid + 1;
}
cout << lf <<"\n";
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
// file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug challenge +2
4
1 2 3 4
2
0 3
2 1
*/
