#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<list>
#include<queue>
#include<string.h>
#include<functional>
#include<stack>
#include<deque>
#include<string>
#include<limits.h>
#include<map>
#include<set>
#include<unordered_map>
#include<cmath>
#include<unordered_set>
using namespace std;

int x, y;
int a[2000][2000];
int c[2000][2000];
int MAX[2000][2002];
int T[2000];
void kaiten() {
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {
			c[i][j] = a[i][j];
		}
	}
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {
			a[y - j - 1][i] = c[i][j];
		}
	}
	swap(x, y);
}
signed main() {
	int MIN = INT_MAX;
	cin >> x >> y;
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {
			cin >> a[i][j];
			MIN = min(MIN, a[i][j]);
		}
	}
	int ans = 1000000000;
	for (int i = 0; i < 4; i++) {
		memset(MAX, 0, sizeof(MAX));
		for (int n = x-1; n >= 0; n--) {
			for (int m = 1; m <= y; m++) {
				MAX[n][m] = max({ MAX[n + 1][m], a[n][m - 1],MAX[n][m-1]});
			}
			MAX[n][y + 1] = INT_MAX;
		}
		int S = -1, G = 1000000000;//[S,G)
		while (G - S > 1) {
			int K = (S + G) / 2;
			for (int i = 0; i < x; i++) {
				for (int j = 1; j <= y+1; j++) {
					if (MAX[i][j] > MIN + K) {
						T[i] = j - 1;
						break;
					}
				}
			}
			int l = INT_MAX, r = 0, n = INT_MAX, m = 0;
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < y; j++) {
					if (T[i] > j) {
						l = min(l, a[i][j]);
						r = max(r, a[i][j]);
					}
					else {
						n = min(n, a[i][j]);
						m = max(m, a[i][j]);
					}
				}
			}
			if (max(r - l, m - n) <= K) {
				G = K;
			}
			else {
				S = K;
			}
		}
		ans = min(ans, G);
		kaiten();
	}
	cout << ans << endl;
}