#include <bits/stdc++.h>
using namespace std;
int n,m,a[2005][2005],b[2005][2005],vmax = 0,vmin = 1e9;
int c[2005][2005];
bool frumoasa(int k)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] < vmax - k)
b[i][j] = 0;
else if (a[i][j] > vmin + k)
b[i][j] = 1;
else
b[i][j] = 2;
if (a[i][j] < vmax - k and a[i][j] > vmin + k)
return false;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
c[i][j] = 0;
for (int i = 1; i <= n; i++)
{
int max0 = 0,min1 = 1e9;
for (int j = 1; j <= m; j++)
{
if (b[i][j] == 0)
max0 = j;
}
for (int j = m; j >= 1; j--)
{
if (b[i][j] == 1)
min1 = j;
}
if (max0 > min1)
return false;
for (int j = 1; j <= max0; j++)
c[i][j] = 1;
for (int j = min1; j <= m; j++)
c[i][j] = 2;
}
for (int j = 1; j <= m; j++)
{
int max0 = 0,min1 = 1e9;
for (int i = 1; i <= n; i++)
{
if (b[i][j] == 0)
max0 = i;
}
for (int i = n; i >= 1; i--)
{
if (b[i][j] == 1)
min1 = i;
}
if (max0 > min1)
return false;
for (int i = 1; i <= max0; i++)
{
if (c[i][j] == 2)
return false;
c[i][j] = 1;
}
for (int i = min1; i <= n; i++)
{
if (c[i][j] == 1)
return false;
c[i][j] = 2;
}
}
return true;
}
void invert_lins()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m / 2; j++)
swap(a[i][j],a[i][m - j + 1]);
}
void invert_cols()
{
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n / 2; i++)
swap(a[i][j],a[n - i + 1][j]);
}
bool pot(int k)
{
///pot face diferenta <= k?
///sa zicem ca cele mai mici o sa fie J-uri
///cele mai mari trebuie sa fie I
///pot pune J doar la valori <= Vmin + k
///pot pune I doar la valori >= Vmax - k
///atunci o sa fixez alea care pot fi doar J sau doar I, restul am libertate sa le pun oricum
///pot oare sa construiesc matricea a.i sa fie frumoasa?
///o matrice frumoasa arata din una din parti astfel: primul rand are prefix maxim de J, apoi ceva mai mic, etc etc etc
if (frumoasa(k) == true)///normala
return true;
invert_lins();
if (frumoasa(k) == true)///privita de la dr la st
return true;
invert_cols();
if (frumoasa(k) == true)///privita complet pe dos
return true;
invert_lins();
if (frumoasa(k) == true)///privita de jos in sus
return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j],vmax = max(vmax,a[i][j]),vmin = min(vmin,a[i][j]);
int st = -1,pas = 1 << 29;
while (pas != 0)
{
if (!pot(st + pas))
st += pas;
pas /= 2;
}
cout << st + 1;
return 0;
}
