#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()
#define lli pair<long long, int>
#define dbg(x) "[" #x " = " << x << "]"
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define left __left
#define right __right
using namespace std;
bool M1;
const long long inf = 1e18 + 123;
const int mod = 1e9 + 7, infINT = 1e9 + 1321, LOG = 32;
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
ll ran(ll l, ll r){
return uniform_int_distribution<ll>(l, r)(rd);
}
void add(int &a, const int &b){
a += b;
if (a >= mod) a -= mod;
}
void sub(int &a, const int &b){
a -= b;
if (a < 0) a += mod;
}
int mul(const int &a, const int &b){
return 1LL * a * 1LL * b % mod;
}
int bin_pow(int a, long long k){
int res = 1;
while(k){
if (k & 1) res = mul(res, a);
k >>= 1; a = mul(a, a);
}
return res;
}
const int MAXN = 2005;
int numRow, numCol, board[MAXN][MAXN], rboard[MAXN][MAXN];
vector<int > comp;
void input(){
cin >> numRow >> numCol;
for(int i = 1; i <= numRow; i++)
for(int j = 1; j <= numCol; j++){
cin >> board[i][j];
comp.push_back(board[i][j]);
rboard[numRow - i + 1][j] = board[i][j];
}
}
bool check(const int &L, const int &R, int board[MAXN][MAXN]){
int mx = 0;
for(int i = 1; i <= numRow; i++){
for(int j = numCol; j >= 1; j--){
if (board[i][j] <= L){
mx = max(mx, j);
}
if (board[i][j] >= R){
if (mx >= j) return 0;
}
}
}
return 1;
}
bool check(const int &mid){
int L = upper_bound(all(comp), comp[0] + mid) - begin(comp) - 1;
int R = lower_bound(all(comp), comp[siz(comp) - 1] - mid) - begin(comp);
if (L + 1 <= R - 1) return 0;
swap(L, R);
L--; R++;
L = comp[L];
R = comp[R];
return (check(L, R, board) || check(L, R, rboard));
}
void solve(){
sort(all(comp));
comp.resize(unique(all(comp)) - begin(comp));
vector<int > can;
for(int x: comp){
can.push_back(x - comp[0]);
can.push_back(comp[siz(comp) - 1] - x);
}
sort(all(can));
can.resize(unique(all(can)) - begin(can));
if (siz(comp) <= 1) return cout << 0 << '\n', void();
int res = infINT;
for(int rot = 0; rot < 2; rot++){
int l = 0, r = siz(can) - 1, m, tmp = infINT;
while(l <= r){
m = (l + r) >> 1;
if (check(can[m])) tmp = can[m], r = m - 1;
else l = m + 1;
}
res = min(res, tmp);
for(int i = 1; i <= numRow; i++){
for(int j = 1; 2 * j <= numCol; j++){
swap(board[i][j], board[i][numCol - j + 1]);
swap(rboard[i][j], rboard[i][numCol - j + 1]);
}
}
}
cout << res << '\n';
cerr << res << '\n';
assert(res != infINT);
}
bool M2;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
input();
solve();
cerr << (&M2 - &M1) / 1048576 << " mb\n";
cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
}
