#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emaplce_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
const int INF = 1e9 + 7, N = 2003;
int a[N][N];
signed main()
{
IO_OP;
int h, w;
cin >> h >> w;
int mx = 0, mn = INF;
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
cin >> a[i][j];
mx = max(mx, a[i][j]);
mn = min(mn, a[i][j]);
}
}
auto ok = [&] (int max_ans) {
auto must_with_mx = [&] (int x) {
return x - mn > max_ans;
};
auto must_with_mn = [&] (int x) {
return mx - x > max_ans;
};
auto yes1 = [&]() {
V<vi> b(h, vi(w));
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
if(must_with_mx(a[i][j]))
b[i][j] = 1;
for(int i = 0; i < h; i++)
for(int j = w - 1; j >= 0; j--) {
if(i + 1 < h) b[i + 1][j] |= b[i][j];
if(j - 1 >= 0) b[i][j - 1] |= b[i][j];
if(b[i][j] && must_with_mn(a[i][j]))
return false;
}
return true;
};
auto yes2 = [&]() {
V<vi> b(h, vi(w));
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
if(must_with_mx(a[i][j]))
b[i][j] = 1;
for(int i = h - 1; i >= 0; i--)
for(int j = w - 1; j >= 0; j--) {
if(i - 1 >= 0) b[i - 1][j] |= b[i][j];
if(j - 1 >= 0) b[i][j - 1] |= b[i][j];
if(b[i][j] && must_with_mn(a[i][j]))
return false;
}
return true;
};
auto yes3 = [&]() {
V<vi> b(h, vi(w));
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
if(must_with_mn(a[i][j]))
b[i][j] = 1;
for(int i = 0; i < h; i++)
for(int j = w - 1; j >= 0; j--) {
if(i + 1 < h) b[i + 1][j] |= b[i][j];
if(j - 1 >= 0) b[i][j - 1] |= b[i][j];
if(b[i][j] && must_with_mx(a[i][j]))
return false;
}
return true;
};
auto yes4 = [&]() {
V<vi> b(h, vi(w));
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
if(must_with_mn(a[i][j]))
b[i][j] = 1;
for(int i = h - 1; i >= 0; i--)
for(int j = w - 1; j >= 0; j--) {
if(i - 1 >= 0) b[i - 1][j] |= b[i][j];
if(j - 1 >= 0) b[i][j - 1] |= b[i][j];
if(b[i][j] && must_with_mx(a[i][j]))
return false;
}
return true;
};
return yes1() || yes2() || yes3() || yes4();
};
int lb = 0, rb = mx - mn - 1;
while(lb <= rb) {
int mb = (lb + rb) / 2;
if(ok(mb))
rb = mb - 1;
else
lb = mb + 1;
}
cout << lb << '\n';
}
