#include<bits/stdc++.h>

using namespace std;

int a[][],n,m,Ans=1e9+,mx,mn=1e9+;

inline bool ck(int x){

    int i,j,k,l=mn+x,r=mx-x,lim=m;

    for(i=;i<=n;i++){

      for(j=;j<=lim;j++)

        if(a[i][j]<r)break;

      lim=min(lim,j-);

      for(j=lim+;j<=m;j++)

        if(a[i][j]>l)return ;

    }

    return ;

}

inline void work(){

    if(ck()){

      puts("");

      exit();

    }

    int le=,ri=mx-mn;

    while(ri-le>){

      int mid=(le+ri)>>;

      if(ck(mid))ri=mid;

        else le=mid;

    }

    Ans=min(Ans,ri);

    return;

}

int main(){

    int i,j,k;

    scanf("%d%d",&n,&m);

    for(i=;i<=n;i++)

      for(j=;j<=m;j++)

        scanf("%d",&a[i][j]),mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);

    work();

    for(i=;i<=n/;i++)swap(a[i],a[n-i+]);

    work();

    for(i=;i<=n;i++)reverse(a[i]+,a[i]+m+);

    work();

    for(i=;i<=n/;i++)swap(a[i],a[n-i+]);

    work();

    cout<<Ans;

    return ;

}