#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int M=0,m=1e9;
vector<vector<int>> mapa(2000, vector<int>(2000));
int w,h;
void rotate90() {
vector<vector<int>> N(2000, vector<int>(2000));
for(int i=0; i<w; ++i) for(int j=0; j<h; ++j) N[i][j] = mapa[j][w-i-1];
swap(mapa,N);
swap(w,h);
}
int solve() {
int lo=0, hi=M-m;
while(lo < hi) {
int mid = (lo+hi)/2;
vector<int> H(w);
int last = 0;
for(int i=0; i<w; ++i) {
int curr = h-1;
while(curr > last && mapa[curr][i] >= M-mid) curr--;
last = H[i] = curr;
}
int maxi = 0, mini = 1e9;
for(int i=0; i<w; ++i) {
for(int j=0; j<H[i]; ++j) {
maxi = max(maxi, mapa[j][i]);
mini = min(mini, mapa[j][i]);
}
}
if(maxi - mini <= mid) hi = mid;
else lo = mid + 1;
}
return lo;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int res = 1e9;
cin >> h >> w;
for(int i=0; i<h; ++i) {
for(int j=0; j<w; ++j) {
cin >> mapa[i][j];
M = max(M,mapa[i][j]);
m = min(m,mapa[i][j]);
}
}
for(int i=0; i<4; ++i) {
res = min(res,solve());
rotate90();
}
cout << res << "\n";
return 0;
}
