#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int high;
int low;
void turn(vector<vector<int> >&);
bool func(vector<vector<vector<int> > >&,int);
bool solve(vector<vector<int> >&,int);
vector<int> getlnum(vector<vector<int> >&,int);
vector<int> gethnum(vector<vector<int> >&,int);
int main(){
    int H,W;
    cin>>H>>W;
    vector<vector<int> > map(W,vector<int>(H));
    vector<vector<vector<int> > > h(4);
    high = 0;
    low = (1<<31)-1;
    for(int y=0;y<H;++y){
        for(int x=0;x<W;++x){
            cin>>map[x][y];
            high = max(map[x][y],high);
            low = min(map[x][y],low);
        }
    }
    for(int i=0;i<4;++i){
        h[i] = map;
        turn(map);
    }
    int lp = 0;
    int hp = high;
    while(lp<hp){
        int mp = (lp+hp)/2;
        if(func(h,mp)){
            hp=mp;
        }else{
            lp=mp+1;
        }
    }
    cout<<lp<<endl;
    return 0;
}

void turn(vector<vector<int> >&map){
    int H=map.size();
    int W = map.front().size();
    vector<vector<int> > res(W,vector<int>(H));
    for(int x=0;x<W;++x){
        for(int y=0;y<H;++y){
            res[x][y] = map[y][W-x-1];
        }
    }
    map=res;
}

bool func(vector<vector<vector<int> > >&map,int num){
    for(int i=0;i<4;++i){
        if(solve(map[i],num)){
            return true;
        }
    }
    return false;
}

bool solve(vector<vector<int> >&map,int num){
    vector<int> lnum,hnum;
    lnum = getlnum(map,0);
    hnum = gethnum(map,0);
    int left = -1;
    if(high-lnum[0]>num){
        bool ok = false;
        for(int x=0;x<map.size()-1;++x){
            if(hnum[x]-low<=num&&high-lnum[x+1]<=num&&left<=x){
                ok=true;
                left=x;
                break;
            }
        }
        if(!ok){
            return false;
        }
    }
    for(int y=1;y<map.front().size()-1;++y){
        lnum = getlnum(map,y);
        hnum = gethnum(map,y);
        if(high-lnum[0]<=num&&left==-1){
            continue;
        }
        bool ok = false;
        for(int x=0;x<map.size()-1;++x){
            if(hnum[x]-low<=num&&high-lnum[x+1]<=num&&left<=x){
                ok=true;
                left=x;
                break;
            }
        }
        if(!ok){
            if(hnum[map.size()-1]-low<=num){
                left=map.size()-1;
            }else{
                return false;
            }
        }
    }
    int y=map.front().size()-1;
    hnum = gethnum(map,y);
    lnum = getlnum(map,y);
    bool ok = false;
    for(int x=0;x<map.size()-1;++x){
        if(hnum[x]-low<=num&&high-lnum[x+1]<=num&&left<=x){
            ok=true;
            left=x;
            break;
        }
    }
    if(!ok){
        if(hnum[map.size()-1]-low<=num){
            left=map.size()-1;
        }else{
            return false;
        }
    }
    return true;
}

vector<int> getlnum(vector<vector<int> >&map,int y){
    vector<int> res(map.size());
    res[map.size()-1]=map[map.size()-1][y];
    for(int x=map.size()-2;x>=0;--x){
        res[x]=min(res[x+1],map[x][y]);
    }
    return res;
}

vector<int> gethnum(vector<vector<int> >&map,int y) {
    vector<int> res(map.size());
    res[0]=map[0][y];
    for(int x=1;x<map.size();++x){
        res[x]=max(res[x-1],map[x][y]);
    }
    return res;
}


Measured memory_bytes: 97040