//The Kingdom of JOIOI
#include <iostream>
#include <unordered_set>
#include <climits>
#include <vector>
#include <string>
#define MIN(a, b) ((a<b)? a :b )
#define MAX(a, b) ((a>b)? a :b )
long long h, w, min, max, col, a, b, min_a, min_b, max_a, max_b;
long long limit, ans;
long long mat[2007][2007];
int loga[2007] = {};
int expbin[12] = {};
//std::set<std::pair<long long, long long>> set;
void b_log(){
long long bin=2;
int cont = 1;
expbin[0]=0;
expbin[1]=1;
for(int i = 1; i<2005; ++i){
if(i>=bin){
bin*=2;
++cont;
expbin[cont]=i;
}
loga[i]=cont;
//std::cout << loga[i] <<'\n';
}
bin = 1;
for(int i = 0; i<11; ++i){
}
}
struct sparse{
std::vector<int> min;
std::vector<int> max;
};
sparse table[2007][2007];
void b_sparse(){
for(int i = h-1; i>=0; --i){
table[col][i].min.push_back(mat[i][col]);
table[col][i].max.push_back(mat[i][col]);
for(int j = 1; j+i<h; j*=2){
//std::cout << '-'<< i+j-j/2 <<' '<<j/2 <<':'<<loga[j/2]<< '_';
table[col][i].min.push_back(MIN(table[col][i].min[loga[j/2]], table[col][i+j-j/2].min[loga[j/2]]));
table[col][i].max.push_back(MAX(table[col][i].max[loga[j/2]], table[col][i+j-j/2].max[loga[j/2]]));
}
/*
for(int x : table[col][i].min){
std::cout << x <<' ';
}
std::cout << '\n';
for(int x : table[col][i].max){
std::cout << x <<' ';
}
std::cout << '\n';
// */
}
}
int min_tree(){
int range=b-a;
//std::cout <<b-expbin[loga[range]] <<" :2nd pos\n";
return MIN(table[col][a].min[loga[range]], table[col][b-expbin[loga[range]]].min[loga[range]]);
}
int max_tree(){
int range=b-a;
return MAX(table[col][a].max[loga[range]], table[col][b-expbin[loga[range]]].max[loga[range]]);
}
struct hF
{
size_t operator()(const std::vector<int> &vec) const
{
std::hash<int> hasher;
size_t answer = 0;
for (int i : vec)
{
answer ^= hasher(i) + 0x9e3779b9 +
(answer << 6) + (answer >> 2);
}
return answer;
}
};
std::unordered_set<std::vector<int>, hF> dp;
std::unordered_set<std::vector<int>, hF> dp2;
void increase(int j, std::unordered_set<std::vector<int>, hF> &sa, std::unordered_set<std::vector<int>, hF> &sb){
for(std::vector<int> x : sa){
//limit, min, max, min, max
/*
std::cout << j<<"pos ";
for(int c : x){
std::cout << c <<' ';
}
std::cout <<'\n';
//*/
limit=x[0];
if(j==w){
ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
continue;
}
col= j;
a=0;
b=h-1;
sb.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});
min=x[1];
max=x[2];
for(int i = 0; i<=limit; ++i){
min = MIN(min, mat[i][j]);
max = MAX(max, mat[i][j]);
a=i+1;
//std::cout << a << ':'<< b << ' ' << i << '\n';
if(a<h){
sb.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
}
else{
sb.insert({i, min, max, x[3], x[4]});
}
}
}
sa.clear();
}
void decrease(int j, std::unordered_set<std::vector<int>, hF> &sa, std::unordered_set<std::vector<int>, hF> &sb){
for(std::vector<int> x : sa){
//limit, min, max, min, max
/*
std::cout << j<<"pos ";
for(int c : x){
std::cout << c <<' ';
}
std::cout <<'\n';
//*/
limit=x[0];
if(j==w){
ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
continue;
}
col= j;
a=0;
b=h-1;
//sb.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});
min=x[1];
max=x[2];
for(int i = 0; i<limit; ++i){
min = MIN(min, mat[i][j]);
max = MAX(max, mat[i][j]);
}
for(int i = limit; i<h; ++i){
if(i>=0){
min = MIN(min, mat[i][j]);
max = MAX(max, mat[i][j]);
}
//std::cout <<min <<':' << max <<'\n';
a=i+1;
if(a<h){
sb.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
}
else{
sb.insert({i, min, max, x[3], x[4]});
}
}
}
sa.clear();
}
int main(){
//std::cin.tie(0);
//std::ios_base::sync_with_stdio(0);
b_log();
std::cin >> h >> w;
for(int i = 0; i<h; ++i){
for(int j = 0; j<w; ++j){
std::cin >> mat[i][j];
//og.insert(mat[i][j]);
}
}
min = LLONG_MAX;
for(int j = 0; j<w; ++j){
col=j;
b_sparse();
}
col = 0;
a = 3;
b = 4;
//std::cout << min_tree() << ' ' << max_tree()<<'\n';
//return 0;
ans = LLONG_MAX;
//ms_b=og;
dp.insert({h-1, 2000123000, 0, 2000123000, 0});
for(int j = 0; j<=w; ++j){
if(j%2==0){
increase(j, dp, dp2);
}
else{
increase(j, dp2, dp);
}
}
//return 0 ;
//std::cout << "prelim: " << ans <<'\n';
dp.clear();
dp2.clear();
dp.insert({-1, 2000123000, 0, 2000123000, 0});
for(int j = 0; j<=w; ++j){
if(j%2==0){
decrease(j, dp, dp2);
}
else{
decrease(j, dp2, dp);
}
}
std::cout << ans;
return 0;
}
