#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; }