#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
using namespace std;
#define INF 0x7f7f7f7f
#define X first
#define Y second
int stage[2005][2005];
int val[2005];
pair<int, int> bound[2005];
bool solve(int H, int W, int aval, int bval, int target)
{
for(int j = 0; j < W; j++)
{
val[j] = H;
for(int i = H-1; i >= 0; i--)
{
if(abs(aval-stage[i][j]) <= target)
val[j] = i;
else
break;
}
}
for(int j = 0; j < W; j++)
{
bound[j] = (val[j] == 0 ? make_pair(0, 0) : make_pair(-1, -1));
for(int i = 0; i < H; i++)
{
if(abs(bval-stage[i][j]) <= target)
{
if(i >= val[j]-1)
{
if(bound[j].X == -1)
bound[j].X = i+1;
bound[j].Y = i+1;
}
}
else
break;
}
if(bound[j].X == -1)
return false;
}
bool ret = 1;
int x = bound[0].Y;
for(int j = 1; j < W; j++)
{
if(x < bound[j].X)
ret = 0;
x = min(x, bound[j].Y);
}
if(ret)
return true;
ret = 1;
x = bound[W-1].Y;
for(int j = W-2; j >= 0; j--)
{
if(x < bound[j].X)
ret = 0;
x = min(x, bound[j].Y);
}
if(ret)
return true;
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int H, W;
cin >> H >> W;
int mn = INF, mx = 0;
for(int i = 0; i < H; i++)
for(int j = 0; j < W; j++)
{
cin >> stage[i][j];
mn = min(mn, stage[i][j]);
mx = max(mx, stage[i][j]);
}
int l = 0, r = mx-mn;
while(l < r)
{
int mid = (l+r) / 2;
if(solve(H, W, mn, mx, mid) || solve(H, W, mx, mn, mid))
r = mid;
else
l = mid+1;
}
cout << l << '\n';
}
