#include <bits/stdc++.h>
using namespace std;
const int nx=2e3+5;
int h, w, mp[nx][nx], l, r, dplmx[nx][nx], dprmx[nx][nx], dplmn[nx][nx], dprmn[nx][nx], mn=INT_MAX;
bool solve1(int x)
{
int pts=w, cmn=INT_MAX, cmx=0;
for (int i=1; i<=h; i++)
{
while (dplmx[i][pts]>mn+x) pts--;
cmn=min(cmn, dprmn[i][pts+1]);
cmx=max(cmx, dprmx[i][pts+1]);
}
return (cmx-cmn)<=x;
}
bool solve2(int x)
{
int pts=w, cmn=INT_MAX, cmx=0;
for (int i=h; i>=1; i--)
{
while (dplmx[i][pts]>mn+x) pts--;
cmn=min(cmn, dprmn[i][pts+1]);
cmx=max(cmx, dprmx[i][pts+1]);
}
return (cmx-cmn)<=x;
}
bool solve3(int x)
{
int pts=1, cmn=INT_MAX, cmx=0;
for (int i=1; i<=h; i++)
{
while (dprmx[i][pts]>mn+x) pts++;
cmn=min(cmn, dplmn[i][pts-1]);
cmx=max(cmx, dplmx[i][pts-1]);
}
return (cmx-cmn)<=x;
}
bool solve4(int x)
{
int pts=1, cmn=INT_MAX, cmx=0;
for (int i=h; i>=1; i--)
{
while (dprmx[i][pts]>mn+x) pts++;
cmn=min(cmn, dplmn[i][pts-1]);
cmx=max(cmx, dplmx[i][pts-1]);
}
return (cmx-cmn)<=x;
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>h>>w;
for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) cin>>mp[i][j], mn=min(mn, mp[i][j]);
for (int i=1; i<=h; i++) dplmn[i][0]=dprmn[i][w+1]=INT_MAX;
for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) dplmx[i][j]=max(dplmx[i][j-1], mp[i][j]), dplmn[i][j]=min(dplmn[i][j-1], mp[i][j]);
for (int i=1; i<=h; i++) for (int j=w; j>=1; j--) dprmx[i][j]=max(dprmx[i][j+1], mp[i][j]), dprmn[i][j]=min(dprmn[i][j+1], mp[i][j]);
l=0, r=1e9;
while (l<r)
{
int md=(l+r)/2;
if (solve1(md)||solve2(md)||solve3(md)||solve4(md)) r=md;
else l=md+1;
}
cout<<l;
}
/*
3 3
1 1 1
10 10 10
1 1
*/
