#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i = a; i < b; i++)
int min_above(vi& arr, int key, int l, int r) {
while(l < r) {
int m = (l+r)/2;
if(arr[m] <= key)
l = m+1;
else
r = m;
}
return r;
}
int search_best(int H, int W, vi& vmin1, vi& vmax1, vi& vmin2, vi& vmax2) {
int from = 0;
int to = 1000000000;
int bestUntilNow = 1000000000;
while(from <= to) {
int mid = (from+to)/2;
int min1, min2, max1, max2;
min1 = min2 = 1000000001;
max1 = max2 = 0;
rep(h,0,H) {
int i = min_above(vmax1, mid, h*W, (h+1)*W);
//if(mid == 24) cerr << h << ": " << i/W << ", " << i%W << '\n';
if(i > h*W) {
min1 = min(min1, vmin1[i-1]);
max1 = max(max1, vmax1[i-1]);
}
if(i < (h+1)*W) {
min2 = min(min2, vmin2[i]);
max2 = max(max2, vmax2[i]);
}
}
int res1 = max1-min1;
int res2 = max2-min2;
//if(vmin1[0] == 18) cerr << "mid = " << mid << ", (from, to) = (" << from << ", " << to << "), (res1, res2) = (" << res1 << ", " << res2 <<")\n";
bestUntilNow = min(bestUntilNow, max(res1, res2));
if(min1 == 0 || min2 == 0 || res1 < res2)
from = mid+1;
else
to = mid-1;
}
return bestUntilNow;
}
int min_above2(vi& arr, int key, int l, int r) {
while(l < r) {
int m = (l+r)/2;
if(arr[m] >= key)
l = m+1;
else
r = m;
}
return r;
}
int search_best2(int H, int W, vi& vmin1, vi& vmax1, vi& vmin2, vi& vmax2) {
int from = 0;
int to = 1000000000;
int bestUntilNow = 1000000000;
while(from < to) {
int mid = (from+to)/2;
int min1, min2, max1, max2;
min1 = min2 = 1000000001;
max1 = max2 = 0;
rep(h,0,H) {
int i = min_above2(vmin1, mid, h*W, (h+1)*W);
if(i > h*W) {
min1 = min(min1, vmin1[i-1]);
max1 = max(max1, vmax1[i-1]);
}
if(i < (h+1)*W) {
min2 = min(min2, vmin2[i]);
max2 = max(max2, vmax2[i]);
}
}
int res1 = max1-min1;
int res2 = max2-min2;
bestUntilNow = min(bestUntilNow, max(res1, res2));
if(max1 == 0 || max2 == 0 || res1 < res2)
from = mid+1;
else
to = mid-1;
}
return bestUntilNow;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int H, W;
cin >> H;
cin >> W;
vi alt1(H*W);
rep(h,0,H)
rep(w,0,W) cin >> alt1[w+h*W];
vi max1(H*W);
vi min1(H*W);
vi max2(H*W);
vi min2(H*W);
vi alt(H*W);
int ans = 1000000000;
rep(j,0,2) {
rep(i,0,4) {
if(i == 0) rep(h,0,H) rep(w,0,W) alt[w+h*W] = alt1[w+h*W];
if(i == 1) rep(h,0,H) rep(w,0,W) alt[w+h*W] = alt1[W-1-w+h*W];
if(i == 2) rep(h,0,H) rep(w,0,W) alt[w+h*W] = alt1[w+(H-1-h)*W];
if(i == 3) rep(h,0,H) rep(w,0,W) alt[w+h*W] = alt1[W-1-w+(H-1-h)*W];
rep(h,0,H) {
rep(w,0,W) {
max1[w+h*W] = alt[w+h*W];
if(w > 0) max1[w+h*W] = max(max1[w+h*W], max1[w-1+h*W]);
if(h > 0) max1[w+h*W] = max(max1[w+h*W], max1[w+(h-1)*W]);
}
}
rep(h,0,H) {
rep(w,0,W) {
min1[w+h*W] = alt[w+h*W];
if(w > 0) min1[w+h*W] = min(min1[w+h*W], min1[w-1+h*W]);
if(h > 0) min1[w+h*W] = min(min1[w+h*W], min1[w+(h-1)*W]);
}
}
rep(h,0,H) {
rep(w1,0,W) {
int w = W-1-w1;
max2[w+h*W] = alt[w+h*W];
if(w < W-1) max2[w+h*W] = max(max2[w+h*W], max2[w+1+h*W]);
}
}
rep(h,0,H) {
rep(w1,0,W) {
int w = W-1-w1;
min2[w+h*W] = alt[w+h*W];
if(w < W-1) min2[w+h*W] = min(min2[w+h*W], min2[w+1+h*W]);
}
}
int res;
if(j == 0) res = search_best(H,W,min1,max1,min2,max2);
if(j == 1) res = search_best2(H,W,min1,max1,min2,max2);
//cerr << res << '\n';
ans = min(ans, res);
}
}
cout << ans << '\n';;
}
