Problem: The Kingdom of JOIOI is a rectangular grid of $H \times W$ cells. In the Kingdom of JOIOI, in order to improve efficiency of administrative institutions, the country will be divided into two regions called "JOI" and "IOI."

Since we do not want to divide it in a complicated way, the division must satisfy the following conditions:

* Each region must contain at least one cell.
* Each cell must belong to exactly one of two regions.
* For every pair of cells in the JOI region, we can travel from one to the other by passing through cells belonging to the JOI region only. When move from a cell to another cell, the two cells must share an edge. The same is true for the IOI region.
* For each row or column, if we take all the cells in that row or column, the cells belonging to each region must be connected. All the cells in a row or column may belong to the same region.



Each cell has an integer called the altitude. After we divide the country into two regions, it is expected that traveling in each region will be active. But, if the difference of the altitudes of cells are large, traveling between them becomes hard. Therefore, we would like to minimize the maximum of the difference of the altitudes between cells belonging to the same region. In other words, we would like to minimize the larger value of

* the difference between the maximum and the minimum altitudes in the JOI region, and
* the difference between the maximum and the minimum altitudes in the IOI region.



Task

Given the altitudes of cells in the Kingdom of JOIOI, write a program which calculates the minimum of the larger value of the difference between the maximum and the minimum altitudes in the JOI region and the difference between the maximum and the minimum altitudes in the IOI region when we divide the country into two regions.

Input

Read the following data from the standard input.

* The first line of input contains two space separated integers $H$, $W$. This means the Kingdom of JOIOI is a rectangular grid of $H \times W$ cells.
* The $i$-th line ($1 \leq i \leq H$) of the following $H$ lines contains $W$ space separated integers $A_{i,1}, A_{i,2}, ..., A_{i,W}$. This means the cell in the $i$-th row from above and $j$-th column from left ($1 \leq j \leq W$) has altitude $A_{i,j}$.



Output

Write one line to the standard output. The output contains the minimum of the larger value of the difference between the maximum and the minimum altitudes in the JOI region and the difference between the maximum and the minimum altitudes in the IOI region when we divide the country into two regions.

Constraints

All input data satisfy the following conditions.

* $2 \leq H \leq 2 000．$
* $2 \leq W \leq 2 000．$
* $1 \leq A_{i, j} \leq 1 000 000 000 (1 \leq i \leq H, 1 \leq j \leq W)．$



Sample Input and Output

Sample Input 1


4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10


Sample Output 1


11


For example, in this sample input, we divide the country into two regions as follows. Here, ‘J’ denotes the JOI region, and ‘I’ denotes the IOI region.

<image>

The following division does not satisfy the condition because, in the third column from left, cells with ‘I’ are not connected.

<image>

Sample Input 2


8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16


Sample Output 2


18





Creative Commonse License

The 16th Japanese Olympiad in Informatics (JOI 2016/2017) Final Round





Example

Input

4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10


Output

11

Solution (in CPP):

Solution:
   #include <bits/stdc++.h>
 
//    #include <boost/multiprecision/cpp_int.hpp>
 #define int long long
 #define inf  1000000007
 #define pa pair<int,int>
 #define ll long long
 #define pal pair<double,double>
 #define ppap pair<pa,int>
  #define PI 3.14159265358979323846
  #define paa pair<int,char>
  #define  mp make_pair
  #define  pb push_back
  #define EPS (1e-8)
                                          
    int dx[8]={0,1,0,-1,1,1,-1,-1};
    int dy[8]={1,0,-1,0,-1,1,1,-1};
                                            using namespace std;
                                   			class pa3{
                                            	public:
                                            	int x;
                                   				int y,z;
                                            	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                            	bool operator < (const pa3 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		 return z<p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                   				bool operator > (const pa3 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		 return z>p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa3 &p) const{
                                            		return x==p.x && y==p.y && z==p.z;
                                            	}
                                            		bool operator != (const pa3 &p) const{
                                            			return !( x==p.x && y==p.y && z==p.z);
                                            	}
                                            
                                            };
                                            
                                            class pa4{
                                            	public:
                                            	int x;
                                            	int y,z,w;
                                            	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                            	bool operator < (const pa4 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		if(z!=p.z)return z<p.z;
                                            		return w<p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator > (const pa4 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		if(z!=p.z)return z>p.z;
                                            		return w>p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa4 &p) const{
                                            		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                            	}
                                            		
                                            
                                            };
                                            class pa2{
                                            	public:
                                            	int x,y;
                                            	pa2(int x=0,int y=0):x(x),y(y) {}
                                            	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                            	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                            	bool operator < (const pa2 &p) const{
                                            		return y != p.y ? y<p.y: x<p.x;
                                            	}
                                            	bool operator > (const pa2 &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa2 &p) const{
                                            		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                            	}
                                            	bool operator != (const pa2 &p) const{
                                            		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                            	}
                                            		
                                            
                                            };
                                            
 
                      
                                string itos( int i ) {
                                ostringstream s ;
                                s << i ;
                                return s.str() ;
                                }
                                 
                                int gcd(int v,int b){
                                	if(v==0) return b;
                                	if(b==0) return v;
                                	if(v>b) return gcd(b,v);
                                	if(v==b) return b;
                                	if(b%v==0) return v;
                                	return gcd(v,b%v);
                                }
                 
                            
                                int mod;
int extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
pa operator+(const pa & l,const pa & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}    
pa operator-(const pa & l,const pa & r) {   
    return {l.first-r.first,l.second-r.second};                                    
}  
                                
                int pr[10000100];
                int inv[10000010];
                
                int beki(int wa,int rr,int warukazu){
                	if(rr==0) return 1%warukazu;
                	if(rr==1) return wa%warukazu;
                	wa%=warukazu;
                	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
                	ll zx=beki(wa,rr/2,warukazu);
                	return (zx*zx)%warukazu;
                }
 
                
    			int comb(int nn,int rr){
    				if(rr<0 || rr>nn || nn<0) return 0;
    				int r=pr[nn]*inv[rr];
    				r%=mod;
    				r*=inv[nn-rr];
    				r%=mod;
    				return r;
    			}
               
                void gya(int ert){
                	pr[0]=1;
                	for(int i=1;i<=ert;i++){
                		pr[i]=(pr[i-1]*i)%mod;
                	}
                		inv[ert]=beki(pr[ert],mod-2,mod);
                	for(int i=ert-1;i>=0;i--){
                		inv[i]=inv[i+1]*(i+1)%mod;
                	}
                }
                
              //   cin.tie(0);
    		//	ios::sync_with_stdio(false);
    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                 //sort(ve.begin(),ve.end(),greater<int>());
 //   mt19937(clock_per_sec);
  //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
      

int a[2020][2020]={},b[2010][2010]={};

int ma,mi;
int h,w;

int c[2020];

pa hoge(){
	int x=0,y=0;
	for(int j=1;j<=w;j++){
		if(c[j]&1)x++;
		else break;
	}
	for(int j=w;j>=1;j--){
		if(c[j]&2)y++;
		else break;
	}
	return mp(x,y);
}

bool cha(int x1,int x2,int y1,int y2){
	int e=0;
	for(int i=1;i<=h;i++){
		
		
		for(int j=1;j<=w;j++){
			c[j]=0;
			if(x1<=a[i][j] && a[i][j]<=x2)c[j]+=1;
			if(y1<=a[i][j] && a[i][j]<=y2)c[j]+=2;
			

			
		}
			pa z=hoge();
	//		cout<<z.first<<" "<<z.second<<endl;
			if(z.first+z.second<w)return 0;
			if(e>z.first)return 0;
		//	if(e>max(e,w-z.second))
			e=max(e,w-z.second);
		//cout<<e<<endl;
	}
	return 1;
}

bool chb(int x1,int x2,int y1,int y2){
	int e=0;
	for(int i=1;i<=h;i++){
		
		
		for(int j=1;j<=w;j++){
			c[j]=0;
			if(x1<=b[i][j] && b[i][j]<=x2)c[j]+=1;
			if(y1<=b[i][j] && b[i][j]<=y2)c[j]+=2;
			

			
		}
			pa z=hoge();
	//		cout<<z.first<<" "<<z.second<<endl;
			if(z.first+z.second<w)return 0;
			if(e>z.first)return 0;
		//	if(e>max(e,w-z.second))
			e=max(e,w-z.second);
		//cout<<e<<endl;
	}
	return 1;
}

bool ch(int r){
	int x1=mi,x2=mi+r;
	int y1=ma-r,y2=ma;
//	cout<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<endl;
	if(cha(x1,x2,y1,y2))return 1;
//	cout<<"=="<<endl;
	if(cha(y1,y2,x1,x2))return 1;
	
	
	if(chb(x1,x2,y1,y2))return 1;
	if(chb(y1,y2,x1,x2))return 1;
	return 0;
}

signed main(){
	
	
   cin.tie(0);
	ios::sync_with_stdio(false);

	cin>>h>>w;
	 ma=-inf,mi=inf;
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
		cin>>a[i][j];
		b[i][w+1-j]=a[i][j];
		ma=max(ma,a[i][j]);
		mi=min(mi,a[i][j]);
	}
	if(ma-mi==0){
		cout<<0<<endl;
		return 0;
	}
	if(ch(0)){
	cout<<0<<endl;
		return 0;
	}
	//return 0;
	int si=0,ue=inf;
	
	
	while(ue-si>1){
		int me=(ue+si)/2;
		
		if(ch(me))ue=me;
		else si=me;
	}
	cout<<ue<<endl;
	
	
	return 0;
	

 
 }