#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	int x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
bool suf(ld a, ld b, ld c, ld d) {
	if (b <= c || d <= a) return 0;
	return 1;
}//[a,b),[c,d)
ll fact(ll i, ll z) {
	ll sum = 1;
	for (ll j = max(z, 2LL); j <= i; j++)
		sum = (sum* j) % Mod;
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%Mod;
		x = x*x%p;
		n >>= 1;
	}
	return res;
}
#define int long long
const long long inf = 4523372036854775807;
const int iinf = 1500000000;
//---------------------------------------------------
//+++++++++++++++++++++++++++++++++++++++++++++++++++
int h, w, ma = -1, mi = inf;
int a[2000][2000];
int b[2000][2000][2];
int c[2000];
int d[2000][2000];
bool low(int t) {
	int p = w;
	int u[2] = { inf,-1 };
	for (int i = 0; i<h; i++) {
		int w2 = w;
		if (i == h - 1) w2 = w - 1;
		for (int j = 0; j<w2; j++) {
			if (a[i][j] - mi>t || j >= p) {
				if (j <= c[i]) {
					return 0;
				}
				u[0] = min(u[0], b[i][j][0]);
				u[1] = max(u[1], b[i][j][1]);
				p = j;
				break;
			}
		}
	}
	if (u[1] - u[0]>t) return 0;
	return 1;
}
int solve() {
	int u = -1;
	for (int i = h - 1; i >= 0; i--) {
		b[i][w - 1][0] = a[i][w - 1];
		b[i][w - 1][1] = a[i][w - 1];
		for (int j = w - 1; j >= 0; j--) {
			if (j<w - 1) {
				b[i][j][0] = min(a[i][j], b[i][j + 1][0]);
				b[i][j][1] = max(a[i][j], b[i][j + 1][1]);
			}
			if (a[i][j] == mi) {
				u = max(u, j);
			}
		}
		c[i] = u;
	}
	int s = -1, e = ma - mi, t;
	while (e - s>1) {
		t = (s + e) / 2;
		if (low(t)) {
			e = t;
		}
		else
			s = t;
	}
	low(t);
	return e;
}
void ui() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			a[i][j] = d[i][j];
		}
	}
}
signed main() {
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> a[i][j];
			ma = max(a[i][j], ma);
			mi = min(a[i][j], mi);
		}
	}
	int ans = min(ma - mi, solve());
	for (int i = 0; i < h; i++) {
		for (int j = w - 1; j >= 0; j--) {
			d[i][w - j - 1] = a[i][j];
		}
	}
	ui();
	ans = min(ans, solve());
	for (int i = h - 1; i >= 0; i--) {
		for (int j = 0; j < w; j++) {
			d[h - i - 1][j] = a[i][j];
		}
	}
	ui();
	ans = min(ans, solve());
	for (int i = 0; i < h; i++) {
		for (int j = w - 1; j >= 0; j--) {
			d[i][w - j - 1] = a[i][j];
		}
	}
	ui();
	ans = min(ans, solve());
	cout << ans << endl;
	getchar(); getchar();
}


Measured memory_bytes: 128100