#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
const int MAX_N = 2000 + 5;
int grid[MAX_N][MAX_N];
bool used[MAX_N][MAX_N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}
auto check = [&](int x) {
bool ok = false;
// // 1)
// {
// int first_min = 1e9;
// int first_max = 0;
// int last_used = m - 1;
// for (int i = 0; i < n; ++i) {
// int prev_used = last_used;
// for (int j = 0; j <= prev_used; ++j) {
// int curr_min = min(first_min, grid[i][j]);
// int curr_max = max(first_max, grid[i][j]);
// if (curr_max - curr_min > x) {
// last_used = j - 1;
// break;
// } else {
// first_min = curr_min;
// first_max = curr_max;
// last_used = j;
// used[i][j] = true;
// }
// }
// }
// int second_min = 1e9;
// int second_max = 0;
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < m; ++j) {
// if (!used[i][j]) {
// second_min = min(second_min, grid[i][j]);
// second_max = max(second_max, grid[i][j]);
// } else {
// used[i][j] = false;
// }
// }
// }
// ok |= second_max - second_min <= x;
// }
// 2)
{
int first_min = 1e9;
int first_max = 0;
int last_used = 0;
for (int i = 0; i < n; ++i) {
int prev_used = last_used;
for (int j = m - 1; j >= prev_used; --j) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
last_used = j + 1;
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = j;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
} else {
used[i][j] = false;
}
}
}
ok |= second_max - second_min <= x;
}
// // 3)
// {
// int first_min = 1e9;
// int first_max = 0;
// int last_used = m - 1;
// for (int i = n - 1; i >= 0; --i) {
// int prev_used = last_used;
// for (int j = 0; j <= prev_used; ++j) {
// int curr_min = min(first_min, grid[i][j]);
// int curr_max = max(first_max, grid[i][j]);
// if (curr_max - curr_min > x) {
// last_used = j - 1;
// break;
// } else {
// first_min = curr_min;
// first_max = curr_max;
// last_used = j;
// used[i][j] = true;
// }
// }
// }
// int second_min = 1e9;
// int second_max = 0;
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < m; ++j) {
// if (!used[i][j]) {
// second_min = min(second_min, grid[i][j]);
// second_max = max(second_max, grid[i][j]);
// } else {
// used[i][j] = false;
// }
// }
// }
// ok |= second_max - second_min <= x;
// }
// 4)
{
int first_min = 1e9;
int first_max = 0;
int last_used = 0;
for (int i = n - 1; i >= 0; --i) {
int prev_used = last_used;
for (int j = m - 1; j >= prev_used; --j) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
last_used = j + 1;
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = j;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
} else {
used[i][j] = false;
}
}
}
ok |= second_max - second_min <= x;
}
// // 5)
// {
// int first_min = 1e9;
// int first_max = 0;
// int last_used = n - 1;
// for (int j = 0; j < m; ++j) {
// int prev_used = last_used;
// for (int i = 0; i <= prev_used; ++i) {
// int curr_min = min(first_min, grid[i][j]);
// int curr_max = max(first_max, grid[i][j]);
// if (curr_max - curr_min > x) {
// last_used = i - 1;
// break;
// } else {
// first_min = curr_min;
// first_max = curr_max;
// last_used = i;
// used[i][j] = true;
// }
// }
// }
// int second_min = 1e9;
// int second_max = 0;
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < m; ++j) {
// if (!used[i][j]) {
// second_min = min(second_min, grid[i][j]);
// second_max = max(second_max, grid[i][j]);
// } else {
// used[i][j] = false;
// }
// }
// }
// ok |= second_max - second_min <= x;
// }
// 6)
{
int first_min = 1e9;
int first_max = 0;
int last_used = n - 1;
for (int j = m - 1; j >= 0; --j) {
int prev_used = last_used;
for (int i = 0; i <= prev_used; ++i) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
last_used = i - 1;
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = i;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
} else {
used[i][j] = false;
}
}
}
ok |= second_max - second_min <= x;
}
// // 7)
// {
// int first_min = 1e9;
// int first_max = 0;
// int last_used = 0;
// for (int j = 0; j < m; ++j) {
// int prev_used = last_used;
// for (int i = n - 1; i >= prev_used; --i) {
// int curr_min = min(first_min, grid[i][j]);
// int curr_max = max(first_max, grid[i][j]);
// if (curr_max - curr_min > x) {
// last_used = i + 1;
// break;
// } else {
// first_min = curr_min;
// first_max = curr_max;
// last_used = i;
// used[i][j] = true;
// }
// }
// }
// int second_min = 1e9;
// int second_max = 0;
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < m; ++j) {
// if (!used[i][j]) {
// second_min = min(second_min, grid[i][j]);
// second_max = max(second_max, grid[i][j]);
// } else {
// used[i][j] = false;
// }
// }
// }
// ok |= second_max - second_min <= x;
// }
// 8)
{
int first_min = 1e9;
int first_max = 0;
int last_used = 0;
for (int j = m - 1; j >= 0; --j) {
int prev_used = last_used;
for (int i = n - 1; i >= prev_used; --i) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
last_used = i + 1;
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = i;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
} else {
used[i][j] = false;
}
}
}
ok |= second_max - second_min <= x;
}
return ok;
};
int l = -1;
int r = 1e9 + 1;
while (l != r - 1) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid;
} else {
l = mid;
}
}
cout << r << '\n';
return 0;
}
/*
1 5
1 2 1 2 1
*/
