#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define fi first #define se second #define lld long double int h, w, mn = 1e9, mx = 0; vector<vector<int>> grid, kt; void obrot() { vector<vector<int>> nowe(w, vector<int>(h)); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { nowe[j][h - i - 1] = grid[i][j]; } } swap(grid, nowe); swap(h, w); } bool solve(int x) { kt.clear(); kt.resize(h, vector<int>(w, 0)); int pop = 0, kon; for (int j = w - 1; j >= 0; j--) { kon = h + 1; for (int i = h - 1; i >= 0; i--) { if (mx - grid[i][j] > x or i < pop) break; kt[i][j] = 1; kon = i; } pop = kon; } int mx0 = 0, mn0 = 1e9, mx1 = 0, mn1 = 1e9, l; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { l = grid[i][j]; if (kt[i][j] == 0) { mx0 = max(mx0, l); mn0 = min(mn0, l); } else { mx1 = max(mx1, l); mn1 = min(mn1, l); } } } if (mx0 - mn0 <= x and mx1 - mn1 <= x) return 1; return 0; } bool czy(int x) { if (x == mx - mn) return 1; bool ok = 0; for (int i = 0; i < 4; i++) { if (solve(x)) ok = 1; obrot(); } if (ok) return 1; return 0; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int x; cin >> h >> w; grid.resize(h, vector<int>(w)); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> x; grid[i][j] = x; mx = max(mx, x); mn = min(mn, x); } } int pocz = 0, kon = mx - mn, sr; while (pocz < kon) { sr = (pocz + kon) / 2; if (czy(sr)) kon = sr; else pocz = sr + 1; } cout << pocz; }