#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
using namespace std;
template<typename T> void uin(T &a, T b) {
if (b < a) {
a = b;
}
}
template<typename T> void uax(T &a, T b) {
if (b > a) {
a = b;
}
}
#define ghost signed
#define left left228
#define right right228
#define complex complex228
#define count count228
#define sin sin228
#define list list228
const int N = 2003;
const int INF = 1e9 + 228;
int res = INF;
int n, m;
int a[N][N];
int left[N], right[N];
int mn = INF, mx = 0;
void solve() {
int l = -1, r = mx - mn;
while (r - l > 1) {
int mid = (l + r) >> 1;
int x = mid;
for (int i = 1; i <= n; ++i) {
left[i] = 0, right[i] = m + 1;
for (int j = 1; j <= m; ++j) {
if (a[i][j] > mn + x && right[i] == m + 1) right[i] = j - 1;
if (a[i][j] < mx - x) left[i] = j;
}
}
bool OK1 = 1, OK2 = 1;
int last1 = left[1], last2 = right[1];
if (left[1] > right[1]) OK1 = OK2 = 0;
for (int i = 2; i <= n; ++i) {
if (max(last1, left[i]) > right[i]) OK1 = 0;
uax(last1, left[i]);
if (min(last2, right[i]) < left[i]) OK2 = 0;
uin(last2, right[i]);
}
if (OK1 || OK2) r = mid;
else l = mid;
}
uin(res, r);
}
ghost main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
uax(mx, a[i][j]);
uin(mn, a[i][j]);
}
}
res = mx - mn;
solve();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m / 2; ++j) {
swap(a[i][j], a[i][m - j + 1]);
}
}
solve();
cout << res << '\n';
return 0;
} // kek ;
// Ого! Кажетсья это $#@!
