#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
const int OO = (int)1e18;
int R, C;
vector<vector<int>> grid;
int minVal = OO, maxVal = -OO;
vector<vector<int>> prefMaxRow, prefMinRow;
vector<vector<int>> suffMaxRow, suffMinRow;
void revRows () {
swap(prefMaxRow, suffMaxRow);
swap(prefMinRow, suffMinRow);
for (int r = 0; r < R; r++) {
reverse(grid[r].begin(), grid[r].end());
reverse(prefMaxRow[r].begin(), prefMaxRow[r].end());
reverse(prefMinRow[r].begin(), prefMinRow[r].end());
reverse(suffMaxRow[r].begin(), suffMaxRow[r].end());
reverse(suffMinRow[r].begin(), suffMinRow[r].end());
}
}
bool valid (int r, int c, int diffUB) {
return ( max(prefMaxRow[r][c] - minVal, maxVal - suffMinRow[r][c+1]) <= diffUB );
}
bool testDiffOrder (int diffUB) {
int incCol = 0, decCol = C;
bool incValid = true, decValid = true;
for (int r = 1; r <= R; r++) {
while (incCol <= C && !valid(r, incCol, diffUB)) {
incCol++;
}
if (incCol > C || !valid(r, incCol, diffUB)) {
incValid = false;
}
while (decCol >= 0 && !valid(r, decCol, diffUB)) {
decCol--;
}
if (decCol < 0 || !valid(r, decCol, diffUB)) {
decValid = false;
}
}
return (incValid || decValid);
}
bool testDiff (int diffUB) {
bool res = false;
res |= testDiffOrder(diffUB);
revRows();
res |= testDiffOrder(diffUB);
revRows();
return res;
}
signed main() {
fastIO();
cin >> R >> C;
grid.assign(R+2, vector<int>(C+2, 0));
for (int r = 1; r <= R; r++) {
for (int c = 1; c <= C; c++) {
cin >> grid[r][c];
minVal = min(minVal, grid[r][c]);
maxVal = max(maxVal, grid[r][c]);
}
}
prefMaxRow.assign(R+2, vector<int>(C+2, -OO));
prefMinRow.assign(R+2, vector<int>(C+2, OO));
suffMaxRow.assign(R+2, vector<int>(C+2, -OO));
suffMinRow.assign(R+2, vector<int>(C+2, OO));
for (int r = 1; r <= R; r++) {
for (int c = 1; c <= C; c++) {
prefMaxRow[r][c] = max(prefMaxRow[r][c-1], grid[r][c]);
prefMinRow[r][c] = min(prefMinRow[r][c-1], grid[r][c]);
}
for (int c = C; c >= 1; c--) {
suffMaxRow[r][c] = max(suffMaxRow[r][c+1], grid[r][c]);
suffMinRow[r][c] = min(suffMinRow[r][c+1], grid[r][c]);
}
}
int ansLo = -1, ansHi = OO;
while (ansHi - ansLo > 1) {
int ansMid = ansLo + (ansHi - ansLo) / 2;
if (testDiff(ansMid)) {
ansHi = ansMid;
}
else {
ansLo = ansMid;
}
}
cout << ansHi << "\n";
}
