#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>; ll MM = 2010; ll inf = 1e18; ll M=0,m=inf; vector<vector<ll>> mapa(MM, vector<ll>(MM)); ll w,h; void rotate90() { vector<vector<ll>> N(MM, vector<ll>(MM)); for(ll i=0; i<w; ++i) for(ll j=0; j<h; ++j) N[i][j] = mapa[j][w-i-1]; swap(mapa,N); swap(w,h); } ll solve() { ll lo=0, hi=M-m; while(lo < hi) { ll mid = (lo+hi)/2; vector<ll> H(w); ll last = 0; for(ll i=0; i<w; ++i) { ll curr = h-1; while(curr > last && mapa[curr][i] >= M-mid) curr--; last = H[i] = curr; } ll maxi = 0, mini = inf; for(ll i=0; i<w; ++i) { for(ll 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); ll res = inf; cin >> h >> w; for(ll i=0; i<h; ++i) { for(ll j=0; j<w; ++j) { cin >> mapa[i][j]; M = max(M,mapa[i][j]); m = min(m,mapa[i][j]); } } for(ll i=0; i<4; ++i) { res = min(res,solve()); rotate90(); } cout << res << "\n"; return 0; }