#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
using namespace std;
const int N = 2e3 + 3;
int a[N][N],n,m,mn,mx,cnt[3][N];
bool vis[N][N],cur[3][N][N];
void clear(){
for (int i=1;i<=n;i++)
for(int j = 1; j <= m;j++)
vis[i][j]=0;
}
void go(int x,int y,int d){
if (x < 1 || y < 1 || x > n || y > m || vis[x][y]) return;
if (a[x][y] - mn > d) return;
vis[x][y] = 1;
go(x+1,y,d);
go(x-1,y,d);
go(x,y+1,d);
go(x,y-1,d);
}
int get(bool k){
int mn1=-1,mx1=-1,mn2=-1,mx2=-1;
for (int i= 1; i <= n; i++){
for (int j= 1;j<=m;j++){
if(cur[k][i][j]){
if (mn1 == -1) {
mn1 = mx1 = a[i][j];
}else{
mn1 = min(mn1,a[i][j]);
mx1 = max(mx1,a[i][j]);
}
}else{
if (mn2 == -1) {
mn2 = mx2 = a[i][j];
}else{
mn2 = min(mn2,a[i][j]);
mx2 = max(mx2,a[i][j]);
}
}
}
}
return max(mx2-mn2,mx1-mn1);
}
bool go1(int d){
int mn0 = 2e9,mn1 = 2e9;
for (int i = 1; i <= n; i++){
mn0 = min(mn0,cnt[0][i]);
int l0 = m - mn0 + 1,r0 = m;
mn1 = min(mn1,cnt[1][i]);
int l1 = 1,r1 = mn1;
for (int j = 1; j <= m; j++){
cur[1][i][j] = (j >= l1 && j <= r1);
cur[0][i][j] = (j >= l0 && j <= r0);
}
}
return (get(0) <= d) || (get(1) <= d);
}
bool go2(int d){
int mn0 = 2e9,mn1 = 2e9;
for (int i = n; i >= 1; i--){
mn0 = min(mn0,cnt[0][i]);
int l0 = m - mn0 + 1,r0 = m;
mn1 = min(mn1,cnt[1][i]);
int l1 = 1,r1 = mn1;
for (int j = 1; j <= m; j++){
cur[1][i][j] = (j >= l1 && j <= r1);
cur[0][i][j] = (j >= l0 && j <= r0);
}
}
return (get(0) <= d) || (get(1) <= d);
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
cin>>n>>m;
mn = 2e9;
int X = 0,Y=0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
if (a[i][j] < mn){
X=i,Y=j;
mn=a[i][j];
}
mx=max(mx,a[i][j]);
}
}
int l = 0,r = mx - mn,ans=mx-mn;
while (l <= r){
clear();
int mid=(l+r)/2;
go(X,Y,mid);
for (int i = 1; i <= n; i++){
cnt[0][i] = m;
for (int j = m; j >= 1; j--){
if (!vis[i][j]){
cnt[0][i] = m - j;
break;
}
}
cnt[1][i] = m;
for (int j = 1; j <= m; j++){
if (!vis[i][j]){
cnt[1][i] = j - 1;
break;
}
}
}
if (go1(mid) || go2(mid)){
ans = mid;
r = mid-1;
}else{
l = mid + 1;
}
}
cout<<ans<<endl;
}
