#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>
using namespace std;
const int INF = 1e18;
const int maxn = 2e3 + 7;
int dx[4] = {-1 , 1 , 0 , 0};
int dy[4] = {0 , 0 , -1 , 1};
int n , m , a[maxn][maxn] , b[maxn][maxn];
pii mxpos = {0 , 0};
bool in(int i , int j) {return (1 <= i && i <= n && 1 <= j && j <= m);}
void dfs(int i , int j , int lim)
{
b[i][j] = 1;
for(int k = 0; k < 4; k++)
{
int x = i + dx[k] , y = j + dy[k];
if(in(x , y) && b[x][y] == 0 && a[x][y] >= lim)
{
dfs(x , y , lim);
}
}
}
bool check(int mid)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++) b[i][j] = 0;
}
dfs(mxpos.fi , mxpos.se , a[mxpos.fi][mxpos.se] - mid);
// for(int i = 1; i <= n; i++)
// {
// for(int j = 1; j <= m; j++) cout << b[i][j] << ' ';
// cout << '\n';
// }
int mx = 0 , mn = INF , last = INF;
for(int i = 1; i <= n; i++)
{
int c = 0;
while(c < m && b[i][c+1] == 1) c++;
c = min(c , last);
for(int j = c+1; j <= m; j++)
{
mx = max(mx , a[i][j]);
mn = min(mn , a[i][j]);
}
}
if(mx - mn <= mid || mx == 0)
{
return 1;
}
mx = 0 , mn = INF , last = INF;
for(int i = n; i >= 1; i--)
{
int c = 0;
while(c < m && b[i][c+1] == 1) c++;
c = min(c , last);
for(int j = c+1; j <= m; j++)
{
mx = max(mx , a[i][j]);
mn = min(mn , a[i][j]);
}
}
if(mx - mn <= mid || mx == 0)
{
return 1;
}
mx = 0 , mn = INF , last = 0;
for(int i = 1; i <= n; i++)
{
int c = m+1;
while(c > 1 && b[i][c-1] == 1) c--;
c = max(c , last);
for(int j = 1; j < c; j++)
{
mx = max(mx , a[i][j]);
mn = min(mn , a[i][j]);
}
}
if(mx - mn <= mid || mx == 0)
{
return 1;
}
mx = 0 , mn = INF , last = 0;
for(int i = n; i >= 1; i--)
{
int c = m+1;
while(c > 1 && b[i][c-1] == 1) c--;
c = max(c , last);
for(int j = 1; j < c; j++)
{
mx = max(mx , a[i][j]);
mn = min(mn , a[i][j]);
}
}
if(mx - mn <= mid || mx == 0) return 1;
return 0;
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
if(a[i][j] >= a[mxpos.fi][mxpos.se]) mxpos = (pii){i , j};
}
}
int l = 0 , r = 1e9 , ans = 1e9;
while(l <= r)
{
int mid = (l+r)>>1;
if(check(mid))
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
