/*huypheu
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
*/
//https://oj.uz/problem/view/JOI17_joioi
#include <bits/stdc++.h>
using namespace std;
int mi[2007][3],ma[2007][3];
int a[2007][2007],ty[2007][2007],val[2007];
vector <int> v;
int n,m;
int mak,mik;
bool checko()
{
for(int i=1;i<=n;i++) mi[i][1]=0,ma[i][1]=0,mi[i][2]=m+1,ma[i][2]=m+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ty[i][j]==1) mi[i][1]=j,ma[i][1]=j;
if(ty[i][j]==3) ma[i][1]=j;
if(ty[i][j]==2) break;
}
for(int j=m;j>=1;j--)
{
if(ty[i][j]==2) mi[i][2]=j,ma[i][2]=j;
if(ty[i][j]==3) ma[i][2]=j;
if(ty[i][j]==1) break;
}
if(ma[i][1]<ma[i][2]-1) return 0;
}
bool ok=0;
for(int i=1;i<=n;i++)
{
if(i==1) val[i]=mi[i][1]; else
{
int k=max(val[i-1],mi[i][1]);
if(k<=ma[i][1]) val[i]=k; else break;
}
if(i==n) ok=1;
}
if(ok) return 1;
for(int i=1;i<=n;i++)
{
if(i==1) val[i]=ma[i][1]; else
{
int k=min(val[i-1],ma[i][1]);
if(k>=mi[i][1]) val[i]=k; else break;
}
if(i==n) ok=1;
}
if(ok) return 1;
return 0;
}
bool check(int len)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]<=mik+len) ty[i][j]=1;
if(a[i][j]>=mak-len) ty[i][j]=2;
if(a[i][j]<=mik+len && a[i][j]>=mak-len) ty[i][j]=3;
if(a[i][j]>mik+len && a[i][j]<mak-len) return 0;
}
}
if(checko()) return 1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]>=mik+len) ty[i][j]=1;
if(a[i][j]<=mak-len) ty[i][j]=2;
if(a[i][j]<=mik+len && a[i][j]>=mak-len) ty[i][j]=3;
if(a[i][j]>mik+len && a[i][j]<mak-len) return 0;
}
}
if(checko()) return 1;
return 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin >> a[i][j];
}
}
mik=a[1][1],mak=a[1][1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
mik=min(mik,a[i][j]);
mak=max(mak,a[i][j]);
}
}
int l=0,r=(mak-mik);
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid; else l=mid+1;
}
cout << l << endl;
return 0;
}
