#include <bits/stdc++.h>
using namespace std;
int H; // liczba wierszy
int W; // liczba kolumn
vector<vector<int>> altitude;
vector<vector<int>> occupation;
vector<vector<int>> cnt_x;
vector<vector<int>> cnt_o;
int maxi = 0, mini = 1e9+7;
void occupation_for_delta(int d) {
for (int i=1; i<=H; i++) {
for (int j=1; j<=W; j++) {
const auto& now = altitude[i][j];
bool first = abs(mini - now) <= d;
bool second = abs(maxi - now) <= d;
if (first && second) occupation[i][j] = 0;
else if (first) occupation[i][j] = 1;
else if (second) occupation[i][j] = 2;
else occupation[i][j] = 3;
}
}
}
void count_prefix_sums() {
for (int i=0; i<=H+1; i++) {
cnt_x[i][0] = 0;
cnt_o[i][0] = 0;
}
for (int j=0; j<=W+1; j++) {
cnt_x[0][j] = 0;
cnt_o[0][j] = 0;
}
for (int i=1; i<=H+1; i++) {
for (int j=1; j<=W+1; j++) {
cnt_x[i][j] = cnt_x[i-1][j] + cnt_x[i][j-1] - cnt_x[i-1][j-1];
cnt_o[i][j] = cnt_o[i-1][j] + cnt_o[i][j-1] - cnt_o[i-1][j-1];
if (i <= H && j <= W) {
cnt_x[i][j] += (occupation[i][j] == 1);
cnt_o[i][j] += (occupation[i][j] == 2);
}
}
}
}
int sum(vector<vector<int>>& cnt, int i1, int j1, int i2, int j2) {
if (i1 > i2) swap(i1, i2);
if (j1 > j2) swap(j1, j2);
return cnt[i2][j2] - cnt[i1-1][j2] - cnt[i2][j1-1] + cnt[i1-1][j1-1];
}
bool check_occupation() {
// przejście po wierszach
for (int i=1; i<=H; i++) {
// sprawdzam wiersz
bool x = false; // occ = 1
bool o = false; // occ = 2
int first_found = 0;
for (int j=1; j<=W; j++) {
if (occupation[i][j] == 1) {
x = true;
if (first_found == 0) first_found = 1;
if (first_found == 1 && o) return false;
}
else if (occupation[i][j] == 2) {
o = true;
if (first_found == 0) first_found = 2;
if (first_found == 2 && x) return false;
}
else if (occupation[i][j] == 3) {
return false;
}
}
}
// przejście po kolumnach
for (int j=1; j<=W; j++) {
// sprawdzam kolumnę
bool x = false; // occ = 1
bool o = false; // occ = 2
int first_found = 0;
for (int i=1; i<=H; i++) {
if (occupation[i][j] == 1) {
x = true;
if (first_found == 0) first_found = 1;
if (first_found == 1 && o) return false;
}
else if (occupation[i][j] == 2) {
o = true;
if (first_found == 0) first_found = 2;
if (first_found == 2 && x) return false;
}
else if (occupation[i][j] == 3) {
return false;
}
}
}
// przejście po rogach
vector<int> cnt(4);
cnt[occupation[1][1]]++;
cnt[occupation[1][W]]++;
cnt[occupation[H][1]]++;
cnt[occupation[H][W]]++;
if (cnt[1] == 4 || cnt[2] == 4) return false;
// przejście po ćwiartkach
count_prefix_sums();
for (int i=1; i<=H; i++) {
for (int j=1; j<=W; j++) {
if (occupation[i][j] == 1) {
int a = sum(cnt_o, 1,1, i,j);
int b = sum(cnt_o, 1,W, i,j);
int c = sum(cnt_o, H,1, i,j);
int d = sum(cnt_o, H,W, i,j);
// cout << "(" << i << "," << j << ") " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
if (a && b && c && d) return false;
}
if (occupation[i][j] == 2) {
int a = sum(cnt_x, 1,1, i,j);
int b = sum(cnt_x, 1,W, i,j);
int c = sum(cnt_x, H,1, i,j);
int d = sum(cnt_x, H,W, i,j);
// cout << "(" << i << "," << j << ") " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
if (a && b && c && d) return false;
}
}
}
return true;
}
void print_occupation() {
vector<char> temp = { '.', 'x', 'o', '@' };
for (int i=1; i<=H; i++) {
for (int j=1; j<=W; j++) cout << temp[occupation[i][j]];
cout << '\n';
}
}
void print_prefix_sums() {
for (int i=1; i<=H; i++) {
for (int j=1; j<=W; j++) cout << cnt_x[i][j] << ' ';
cout << '\n';
}
cout << '\n';
for (int i=1; i<=H; i++) {
for (int j=1; j<=W; j++) cout << cnt_o[i][j] << ' ';
cout << '\n';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> H >> W;
altitude.assign(H+1, vector<int>(W+1, 0));
occupation.assign(H+1, vector<int>(W+1, 0));
cnt_o.assign(H+2, vector<int>(W+2, 0));
cnt_x.assign(H+2, vector<int>(W+2, 0));
for (int i=1; i<=H; i++) for (int j=1; j<=W; j++) {
cin >> altitude[i][j];
maxi = max(maxi,altitude[i][j]);
mini = min(mini, altitude[i][j]);
}
int low = 0;
int high = maxi + 7;
while (low != high) {
int mid = (low + high) / 2;
occupation_for_delta(mid);
if (check_occupation()) high = mid;
else low = mid + 1;
}
cout << low << '\n';
}
