#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
vector<vector<long long>> grid;
vector<pair<long long,long long>> moves = {{0,-1},{0,1},{-1,0},{1,0}};
long long h,w;
multiset<long long> ogvals;
bool is_valid_split(const vector<vector<bool>>& vis) {
// Check row connectivity
for (int i = 0; i < h; ++i) {
bool in_region = false;
for (int j = 0; j < w; ++j) {
if (vis[i][j]) {
if (!in_region) in_region = true;
} else {
if (in_region) return false; // Non-contiguous JOI region in row
}
}
}
// Check column connectivity
for (int j = 0; j < w; ++j) {
bool in_region = false;
for (int i = 0; i < h; ++i) {
if (vis[i][j]) {
if (!in_region) in_region = true;
} else {
if (in_region) return false; // Non-contiguous JOI region in column
}
}
}
return true;
}
long long bfs(long long mid){
multiset<long long> vals = ogvals;
queue<pair<pair<long long,long long>,pair<long long,long long>>> nodes;
long long first = grid[0][0];
long long iteration = 0;
nodes.push({{0,0},{first,iteration}});
vals.erase(first);
vector<vector<bool>> vis;
vis.resize(h,vector<bool>(w,false));
vis[0][0] = true;
long long minjoi = first;
long long maxjoi = first;
while (!nodes.empty()){
long long cr = nodes.front().first.first;
long long cc = nodes.front().first.second;
long long cval = nodes.front().second.first;
long long citer = nodes.front().second.second;
nodes.pop();
for(auto move : moves){
long long nr = cr + move.first;
long long nc = cc + move.second;
if (nr >= 0 && nr < h && nc >= 0 && nc < w && vis[nr][nc] != true){
long long newval = grid[nr][nc];
long long new_minjoi = min(minjoi, newval);
long long new_maxjoi = max(maxjoi, newval);
long long difference = new_maxjoi - new_minjoi;
if (difference <= mid) {
// Valid node for JOI region
minjoi = new_minjoi;
maxjoi = new_maxjoi;
vis[nr][nc] = true;
nodes.push({{nr, nc}, {newval, citer + 1}});
}
//else if (difference == mid){
//auto it = prev(vals.end());
//auto it2 = vals.begin();
//long long maxdiff = *it - *it2;
//nodes.push({{nr,nc},{newval,citer + 1}});
//return max(difference,maxdiff);
//}
}
}
}
//for(int i = 0;i<h;i++){
//bool x = true;
//for(int j = 0;j<w;j++){
//if (vis[i][0] == true && vis[i][w-1] == true && vis[i][j] == false && j != w-1){
//return 1e9;
//}
//if (vis[i][w-1] == false && vis[i][0] == false && vis[i][j] == true && j != 0){
//return 1e9;
//}
//if (vis[0][j] == true && vis[h-1][j] == true && vis[i][j] == false && i != h-1){
//return 1e9;
//}
//if (vis[h-1][j] == false && vis[0][j] == false && vis[i][j] == true && i != 0){
//return 1e9;
//}
//}
//}
if (!is_valid_split(vis)) return 1e9;
long long minioi = LLONG_MAX, maxioi = LLONG_MIN;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (!vis[i][j]) {
minioi = min(minioi, grid[i][j]);
maxioi = max(maxioi, grid[i][j]);
}
}
}
cout << maxioi << ' ' << minioi << '\n';
//if (!vals.empty()) {
//auto it = prev(vals.end());
//auto it2 = vals.begin();
//long long maxdiff = abs(*it - *it2);
//cout << difference << ' ' << maxdiff << '\n';
//return max(difference, maxdiff);
//}
//cout << difference << '\n';
if (minioi == LLONG_MAX && maxioi == LLONG_MIN) {
return 1e9;
}
else if (minioi == LLONG_MAX && maxioi != LLONG_MIN){
return max(maxjoi - minjoi,0LL);
}
else if (minioi != LLONG_MAX && maxioi == LLONG_MIN){
return max(maxjoi - minjoi, 0LL);
}
return max(maxjoi - minjoi, maxioi - minioi);
}
bool check(long long mid){
long long r = bfs(mid);
return r <= mid;
}
void bsearch(){
long long lb = 0;
long long ub = 1e9;
long long mid = -1;
long long res = -1;
while (lb <= ub){
mid = (lb + ub) / 2;
if (check(mid)){
res = mid;
ub = mid - 1;
}
else{
lb = mid + 1;
}
}
cout << res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> h >> w;
grid.resize(h,vector<long long>(w));
for(int i = 0;i<h;i++){
for(int j = 0;j<w;j++){
long long alt;cin >> alt;
grid[i][j] = alt;
ogvals.insert(alt);
}
}
bsearch();
}
