#include <bits/stdc++.h>
using namespace std;
#define int long long
const int H = 2000;
int a[H][H];
int h, w, mi, ma;
void pre() {
mi = 1e18, ma = -1;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++)
mi = min(mi, a[i][j]), ma = max(ma, a[i][j]);
}
}
bool check(int dif) {
int ll = mi + dif + 1, ul = ma - dif - 1;
bool track[h][w] = {};
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (a[i][j] >= ll)
track[i][j] = true;
}
}
for (int i = 0; i < h; i++) {
int li = w, hi = -1;
for (int j = 0; j < w; j++) {
if (track[i][j])
li = min(li, j), hi = max(hi, j);
}
for (int j = li; j <= hi; j++) {
if (a[i][j] <= ul)
return false;
track[i][j] = true;
}
}
for (int j = 0; j < w; j++) {
int li = h, hi = -1;
for (int i = 0; i < h; i++) {
if (track[i][j])
li = min(li, i), hi = max(hi, i);
}
for (int i = li; i <= hi; i++) {
if (a[i][j] <= ul)
return false;
track[i][j] = true;
}
}
bool check = true;
for (int i = h - 1, max_ind = -1; i >= 0; i--) {
for (int j = 0; j < w; j++) {
if (track[i][j])
max_ind = max(max_ind, j);
}
for (int j = 0; j <= max_ind; j++) {
if (a[i][j] <= ul)
check = false;
}
}
if (check)
return true;
check = true;
for (int i = 0, max_ind = -1; i < h; i++) {
for (int j = 0; j < w; j++) {
if (track[i][j])
max_ind = max(max_ind, j);
}
for (int j = 0; j <= max_ind; j++) {
if (a[i][j] <= ul)
check = false;
}
}
if (check)
return true;
check = true;
for (int i = h - 1, min_ind = w; i >= 0; i--) {
for (int j = 0; j < w; j++) {
if (track[i][j])
min_ind = min(min_ind, j);
}
for (int j = w - 1; j >= min_ind; j--) {
if (a[i][j] <= ul)
check = false;
}
}
if (check)
return true;
check = true;
for (int i = 0, min_ind = w; i < h; i++) {
for (int j = 0; j < w; j++) {
if (track[i][j])
min_ind = min(min_ind, j);
}
for (int j = w - 1; j >= min_ind; j--) {
if (a[i][j] <= ul)
check = false;
}
}
if (check)
return true;
return false;
}
void solveTestCase() {
cin >> h >> w;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++)
cin >> a[i][j];
}
pre();
int lo = 0, hi = 1e9, ans = 1e9;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(mid))
ans = mid, hi = mid - 1;
else
lo = mid + 1;
}
cout << ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
// cin >> test;
for (int i = 1; i <= test; i++)
solveTestCase();
}
