#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);
int rng() {
return ui(mrand);
}
const int N=2001;
int grid[N][N];
int vals[N*N];
vector<pair<int,int>> pos[N*N];
int n,m;
int diff;
int Min[N][N],Max[N][N];
int suffMin[N*N];
bool can(int mid) {
int p=0;
int curr_min=1<<30,curr_max=0;
for (int i=0;i<diff;i++) {
// this is the 'lower' max
// cout << "I'm saying " << vals[i] << " is the current max " << endl;
while(vals[i]-vals[p]>mid) {
for (auto &[x,y]: pos[p]) {
// cout << "therefore I gotta erase pos " << x << ", " << y << " with value " << grid[x][y] << endl;
cmin(curr_min,Min[x][y]),cmax(curr_max,Max[x][y]);
}
p++;
}
// cout << "which leads to Min = " << curr_min << ", Max = " << curr_max << endl;
if ((i + 1 == diff ? curr_max:vals[diff-1]) - min(suffMin[i+1],curr_min) <= mid)
return 1;
}
return 0;
}
int work() {
int lo=0,hi=1<<30;
while(lo<hi) {
int mid=lo+(hi-lo)/2;
if (can(mid))
hi=mid;
else
lo=mid+1;
}
return lo;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++) {
cin >> grid[i][j];
vals[m*i+j]=grid[i][j];
}
sort(vals,vals+n*m);
diff=unique(vals,vals+n*m)-vals;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
pos[lower_bound(vals,vals+diff,grid[i][j])-vals].emplace_back(i,j);
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
Max[i][j]=Min[i][j]=grid[i][j];
for (int i=0;i<n;i++)
for (int j=0;j<m;j++) {
if (i > 0)
cmax(Max[i][j],Max[i-1][j]);
if (j > 0)
cmax(Max[i][j],Max[i][j-1]);
if (i > 0)
cmin(Min[i][j],Min[i-1][j]);
if (j > 0)
cmin(Min[i][j],Min[i][j-1]);
}
suffMin[diff]=1<<30;
for (int i=diff-1;i>=0;i--) {
suffMin[i]=suffMin[i+1];
for (auto &[x,y]: pos[i]) {
cmin(suffMin[i],Min[x][y]);
}
}
int ans=work();
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
Max[i][j]=Min[i][j]=grid[i][j];
for (int i=0;i<n;i++)
for (int j=m-1;j>=0;j--) {
if (i > 0)
cmax(Max[i][j],Max[i-1][j]);
if (j + 1 < m)
cmax(Max[i][j],Max[i][j+1]);
if (i > 0)
cmin(Min[i][j],Min[i-1][j]);
if (j + 1 < m)
cmin(Min[i][j],Min[i][j+1]);
}
suffMin[diff]=1<<30;
for (int i=diff-1;i>=0;i--) {
suffMin[i]=suffMin[i+1];
for (auto &[x,y]: pos[i]) {
cmin(suffMin[i],Min[x][y]);
}
}
int ans2=work();
cout << min(ans,ans2) << "\n";
}
