//clever
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define DBG(x) cerr << #x << " = " << (x) << endl
#define SZ(x) ((int) ((x).size()))
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define INF 1000000007
#define MAXN 2013
typedef pair<int, int> pii;
int N, M;
int grid[MAXN][MAXN];
int big, small = INF;
pii bigpos, smallpos;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
pii range[MAXN];
bitset<MAXN> cb[MAXN], cs[MAXN];
bool valid(int x, int y)
{
return (0 <= x && x < N && 0 <= y && y < M);
}
bool ok()
{
//these are the first guys that do not approve!
FOR(i, 0, N)
{
if (range[i].fi >= range[i].se) return false;
}
bool flag = true; int pos = 0;
FOR(i, 0, N)
{
//the guy can be in the range (range[i].fi, range[i].se)
if (range[i].se < pos)
{
flag = false; break;
}
pos = max(pos, range[i].fi + 1);
}
if (flag) return true;
flag = true; pos = M - 1;
FOR(i, 0, N)
{
if (range[i].fi > pos)
{
flag = false; break;
}
pos = min(pos, range[i].se - 1);
}
if (flag) return true;
return false;
}
bool check(int c)
{
//try to merge stuff with small!
FOR(i, 0, N)
{
cb[i].reset();
cs[i].reset();
}
queue<pii> q;
q.push(bigpos);
cb[bigpos.fi][bigpos.se] = 1;
while(!q.empty())
{
int x = q.front().fi, y = q.front().se;
q.pop();
FOR(d, 0, 4)
{
pii p = {x + dx[d], y + dy[d]};
if (valid(p.fi, p.se) && (grid[p.fi][p.se] >= big - c) && !(cb[p.fi][p.se]))
{
q.push(p);
cb[p.fi][p.se] = 1;
}
}
}
q.push(smallpos);
cs[smallpos.fi][smallpos.se] = 1;
while(!q.empty())
{
int x = q.front().fi, y = q.front().se;
q.pop();
FOR(d, 0, 4)
{
pii p = {x + dx[d], y + dy[d]};
if (valid(p.fi, p.se) && (grid[p.fi][p.se] <= small + c) && !cs[p.fi][p.se])
{
q.push(p);
cs[p.fi][p.se] = 1;
}
}
}
//try to have SMALL be an increasing/decreasing sequence!
FOR(i, 0, N)
{
for (range[i].se = 0; range[i].se < M; range[i].se++)
{
if (!cs[i][range[i].se]) break;
}
for (range[i].fi = M - 1; range[i].fi >= 0; range[i].fi--)
{
if (!cb[i][range[i].fi]) break;
}
}
if (ok())
{
return true;
}
//try to have BIG be an increasing/decreasing sequence
FOR(i, 0, N)
{
for (range[i].se = 0; range[i].se < M; range[i].se++)
{
if (!cb[i][range[i].se]) break;
}
for (range[i].fi = M - 1; range[i].fi >= 0; range[i].fi--)
{
if (!cs[i][range[i].fi]) break;
}
}
if (ok())
{
return true;
}
return false;
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
// cout << fixed << setprecision(10);
// cerr << fixed << setprecision(10);
// if (fopen("file.in", "r"))
// {
// freopen ("file.in", "r", stdin);
// freopen ("file.out", "w", stdout);
// }
cin >> N >> M;
FOR(i, 0, N)
{
FOR(j, 0, M)
{
cin >> grid[i][j];
if (grid[i][j] > big)
{
big = grid[i][j];
bigpos = {i, j};
}
if (grid[i][j] < small)
{
small = grid[i][j];
smallpos = {i, j};
}
}
}
// cerr << smallpos.fi << ' ' << smallpos.se << ' ' << bigpos.fi << ' ' << bigpos.se << endl;
int lo = 0, hi = big - small;
while(hi > lo)
{
int mid = (hi + lo) >> 1;
if (check(mid)) hi = mid;
else lo = mid + 1;
}
cout << lo << '\n';
// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
return 0;
}
/* READ READ READ
* int overflow, maxn too small, special cases (n=1?, two distinct?), cin.tie() interactive
* reread the problem, try small cases
* note down possible sources of error as you go
* do smth instead of nothing
*/
