#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "functional"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

int N, M, K, H, W, L, R;
//long long int N, M, K, H, W, L, R;

class XorShift {
	unsigned int x, y, z, w, t;
public:
	XorShift() {
		x = 133553533;
		y = 314867339;
		z = 664298413;
		w = 999999937;
		t = 0;
	}
	unsigned int rand() {
		t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w & 0x7fffffff;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	XorShift xs;
	cin >> H >> W;
	//H = 5, W = 5;
	K = 1;
	while (K--) {
		vector<vector<int>>v(H, vector<int>(W));
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				cin >> v[i][j];
				//v[i][j] = xs.rand() % 100;
			}
		}
		//for (auto i : v) {
		//	for (auto j : i)cout << j << " ";
		//	cout << endl;
		//}
		int maxi = 0, mini = MOD;
		for (auto i : v)for (auto j : i)maxi = max(maxi, j), mini = min(mini, j);
		R = MOD;
		L = -1;
		while (R - L > 1) {
			int mid = (R + L) / 2;
			int l = -1, r = -1;
			bool flag = true;
			for (int i = 0; i < H; i++) {
				int ll = -1, rr = W - 1;
				for (int j = 0; j < W; j++) {
					if (v[i][j] - mid > mini)ll = j;
					if (v[i][j] < maxi - mid)rr = min(rr, j - 1);
				}
				if (!i) {
					l = ll, r = rr;
					if (rr < ll)flag = false;
				}
				else {
					if (rr < ll)flag = false;
					if (ll > r)flag = false;
					l = min(l, ll);
					r = min(r, rr);
				}
			}
			if (flag) {
				R = mid;
				continue;
			}
			l = -1, r = -1;
			flag = true;
			for (int i = 0; i < H; i++) {
				int ll = -1, rr = W - 1;
				for (int j = 0; j < W; j++) {
					if (v[i][j] - mid > mini)ll = j;
					if (v[i][j] < maxi - mid)rr = min(rr, j - 1);
				}
				if (!i) {
					l = ll, r = rr;
					if (rr < ll)flag = false;
				}
				else {
					if (rr < ll)flag = false;
					if (rr < l)flag = false;
					l = max(l, ll);
					r = max(r, rr);
				}
			}
			if (flag) {
				R = mid;
				continue;
			}
			L = mid;
		}
		int ans = R;
		for (auto &i : v)reverse(i.begin(), i.end());
		R = MOD;
		L = -1;
		while (R - L > 1) {
			int mid = (R + L) / 2;
			int l = -1, r = -1;
			bool flag = true;
			for (int i = 0; i < H; i++) {
				int ll = -1, rr = W - 1;
				for (int j = 0; j < W; j++) {
					if (v[i][j] - mid > mini)ll = j;
					if (v[i][j] < maxi - mid)rr = min(rr, j - 1);
				}
				if (!i) {
					l = ll, r = rr;
					if (rr < ll)flag = false;
				}
				else {
					if (rr < ll)flag = false;
					if (ll > r)flag = false;
					l = min(l, ll);
					r = min(r, rr);
				}
			}
			if (flag) {
				R = mid;
				continue;
			}
			l = -1, r = -1;
			flag = true;
			for (int i = 0; i < H; i++) {
				int ll = -1, rr = W - 1;
				for (int j = 0; j < W; j++) {
					if (v[i][j] - mid > mini)ll = j;
					if (v[i][j] < maxi - mid)rr = min(rr, j - 1);
				}
				if (!i) {
					l = ll, r = rr;
					if (rr < ll)flag = false;
				}
				else {
					if (rr < ll)flag = false;
					if (rr < l)flag = false;
					l = max(l, ll);
					r = max(r, rr);
				}
			}
			if (flag) {
				R = mid;
				continue;
			}
			L = mid;
		}
		cout << min(ans, R) << endl;
		//cout << R << endl;
	}
	return 0;
}


Measured memory_bytes: 18624