#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <immintrin.h>
#ifndef DEBUG
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#endif
using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
//
using ld = long double;
using ll = long long;
using i128 = __int128;
using ull = unsigned long long;
using pll = std::pair<ll, ll>;
using cmpl = std::complex<ld>;
template<typename T>
using oset = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
constexpr ll MOD1 = 998244353;
constexpr ll MOD = 1000000007;
constexpr ll INV2 = 499122177;
constexpr ld PI = 3.141592653589793;
const ld eps = 1e-7;
const ll K = 3;
//const ll C = 200;
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
ld START_TIME = clock();
ll n, m, min1, max1;
std::vector<std::vector<ll>> a;
bool check(ll mid){
std::vector<ll> mxn(m, 0);
mxn[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == min1){
mxn[j] = i + 1;
}
}
}
ll sufmn = 0;
for (int i = m - 1; i >= 0; --i) {
sufmn = std::max(sufmn, mxn[i]);
mxn[i] = sufmn;
}
ll mxdd = n;
for (int i = 0; i < m; ++i) {
while (mxn[i] < mxdd && a[mxn[i]][i] - min1 <= mid){
++mxn[i];
}
mxdd = mxn[i];
}
ll mxdf = 0, mxdf1 = 0;
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
if (i < mxn[j]){
mxdf = std::max(mxdf, a[i][j] - min1);
}
else{
mxdf = std::max(mxdf, max1 - a[i][j]);
}
}
}
mxn.assign(m, 0);
mxn[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == max1){
mxn[j] = i + 1;
}
}
}
sufmn = 0;
for (int i = m - 1; i >= 0; --i) {
sufmn = std::max(sufmn, mxn[i]);
mxn[i] = sufmn;
}
mxdd = n;
for (int i = 0; i < m; ++i) {
while (mxn[i] < mxdd && max1 - a[mxn[i]][i] <= mid){
++mxn[i];
}
mxdd = mxn[i];
}
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
if (i >= mxn[j]){
mxdf1 = std::max(mxdf1, a[i][j] - min1);
}
else{
mxdf1 = std::max(mxdf1, max1 - a[i][j]);
}
}
}
return mxdf <= mid || mxdf1 <= mid;
}
bool check1(ll mid){
std::vector<ll> mxn(m, 0);
mxn[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == min1){
mxn[j] = i + 1;
}
}
}
ll sufmn = 0;
for (int i = 0; i < m; ++i) {
sufmn = std::max(sufmn, mxn[i]);
mxn[i] = sufmn;
}
ll mxdd = n;
for (int i = m - 1; i >= 0; --i) {
while (mxn[i] < mxdd && a[mxn[i]][i] - min1 <= mid){
++mxn[i];
}
mxdd = mxn[i];
}
ll mxdf = 0, mxdf1 = 0;
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
if (i < mxn[j]){
mxdf = std::max(mxdf, a[i][j] - min1);
}
else{
mxdf = std::max(mxdf, max1 - a[i][j]);
}
}
}
mxn.assign(m, 0);
mxn[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == max1){
mxn[j] = i + 1;
}
}
}
sufmn = 0;
for (int i = 0; i < m; ++i) {
sufmn = std::max(sufmn, mxn[i]);
mxn[i] = sufmn;
}
mxdd = n;
for (int i = m - 1; i >= 0; --i) {
while (mxn[i] < mxdd && max1 - a[mxn[i]][i] <= mid){
++mxn[i];
}
mxdd = mxn[i];
}
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
if (i >= mxn[j]){
mxdf1 = std::max(mxdf1, a[i][j] - min1);
}
else{
mxdf1 = std::max(mxdf1, max1 - a[i][j]);
}
}
}
return mxdf <= mid || mxdf1 <= mid;
}
void solve(){
std::cin >> n >> m;
a.resize(n, std::vector<ll>(m));
min1 = 1e18;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
std::cin >> a[i][j];
}
min1 = std::min(min1, *std::min_element(a[i].begin(), a[i].end()));
max1 = std::max(max1, *std::max_element(a[i].begin(), a[i].end()));
}
if (min1 == max1){
std::cout << 0;
return;
}
ll l = 0, r = max1 - min1;
while (r - l > 1){
ll mid = (l + r) / 2;
if (check(mid) || check1(mid)){
r = mid;
}
else{
l = mid;
}
}
std::cout << r;
}
signed main() {
#ifdef DEBUG
std::freopen("/home/anton/CLionProjects/untitled/input.txt", "r", stdin);
#else
// std::freopen("tri.in", "r", stdin); std::freopen("tri.out", "w", stdout);
#endif
std::cin.tie(nullptr)->std::ios_base::sync_with_stdio(false);
int tt = 1;
// std::cin >> tt;
while (tt--) {
solve();
}
#ifdef DEBUG
std::cerr << '\n';
ld TIME = (clock() - START_TIME) / CLOCKS_PER_SEC;
std::cerr << "Time: " << TIME << '\n';
#endif
}
