#include <bits/stdc++.h>
#define int long long
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define INF 100000000000
using namespace std;
const int N = 2005;
int n, m;
int mat[N][N];
pair<int, int> pmm[N][N];
int ourmin, ourmax;
int ind[N];
int ans = 0;
int mini = INF, maxi = -INF;
set<int> el;
vector<int> dist;
void calcpmm(){
for(int i =0 ;i<n;i++){
pmm[i][m-1] = {mat[i][m-1], mat[i][m-1]};
for(int j = m-2;j>=0;j--){
pmm[i][j].first = min(mat[i][j], pmm[i][j+1].first);
pmm[i][j].second = max(mat[i][j], pmm[i][j+1].second);
}
}
}
int findinrange(int l, int u){
int theirmin = INF;
int theirmax = -INF;
ourmin = INF;
ourmax = -INF;
int prevj = m;
for(int i =0 ;i<n;i++){
int j = 0;
for (; (j < prevj) && (mat[i][j] >= l) && (mat[i][j] <= u); j++) {
ourmin = min(mat[i][j], ourmin);
ourmax = max(ourmax, mat[i][j]);
}
prevj = j;
if(j<m){
theirmin = min(pmm[i][j].first, theirmin);
theirmax = max(pmm[i][j].second, theirmax);
}
}
if(ourmin > ourmax || theirmin > theirmax) return INF;
return max(theirmax - theirmin, ourmax - ourmin);
}
int findans(){
calcpmm();
int tr = INF;
int lo = 0;
int hi = maxi - mini;
while(lo<=hi){
int mid = mid(lo, hi);
int temp = findinrange(mini, mini + mid);
int temp1 = findinrange(maxi - mid, maxi);
int tocons = min(temp, temp1);
//cout<<mid<<" "<<temp<<" "<<temp1<<" "<<mini<<" "<<maxi<<endl;
if(tocons <= mid){
tr = min(tr, tocons);
hi = mid-1;
}
else lo = mid + 1;
}
return tr;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
int a[n][m];
for(int i =0 ;i<n;i++){
for(int j = 0;j<m;j++) {
cin >> mat[i][j];
maxi = max(maxi, mat[i][j]);
mini = min(mini, mat[i][j]);
a[i][j] = mat[i][j];
dist.push_back(mat[i][j]);
}
}
sort(dist.begin(), dist.end());
ans = maxi - mini;
ans = min(ans, findans());
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++) mat[i][j] = a[i][m-j-1];
}
//cout<<"INVERTED"<<endl;
ans = min(ans, findans());
/*for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++) mat[i][j] = a[n-i-1][m-j-1];
}
ans = min(ans, findans());
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++) mat[i][j] = a[n-i-1][j];
}
ans = min(ans, findans());*/
cout<<ans<<endl;
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
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
*/
