#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>
using vvi = std::vector<std::vector<int>>;
int shrink_to_right(const int left_max_value, const std::vector<std::vector<int>>& left_max, const std::vector<std::vector<int>>& right_min) {
	int min = INT_MAX;
	std::vector<int> right_pos(left_max.size());
	for (auto i = 0; i < left_max.size(); ++i) {
		right_pos[i] = std::distance(left_max[i].begin(), std::upper_bound(left_max[i].begin(), left_max[i].end(), left_max_value));
	}
	int min_pos = right_min.front().size();
	for (auto i = 0; i < right_min.size(); ++i) {
		min_pos = std::min(min_pos, right_pos[i]);
		if (min_pos < right_min[i].size())
			min = std::min(min, right_min[i][min_pos]);
	}
	int result = min;
	min = INT_MAX;
	min_pos = right_min.front().size();
	for (auto i = 1; i <= right_min.size(); ++i) {
		min_pos = std::min(min_pos, right_pos[right_pos.size() - i]);
		if (min_pos < right_min[right_min.size() - i].size())
			min = std::min(min, right_min[right_min.size() - i][min_pos]);
	}
	return std::max(result, min);
}
int first_less_or_equals(const std::vector<int>& array, const int value) {
	int left = 0;
	int right = array.size();
	while (left < right) {
		auto mid = (left + right) / 2;
		if (array[mid] <= value) right = mid;
		else left = mid + 1;
	}
	return right;
}
int shrink_to_left(const int right_max_value, const std::vector<std::vector<int>>& right_max, const std::vector<std::vector<int>>& left_min) {
	int min = INT_MAX;
	std::vector<int> right_pos(right_max.size());
	for (auto i = 0; i < right_max.size(); ++i) {
		right_pos[i] = first_less_or_equals(right_max[i], right_max_value) - 1;
	}
	int max_pos = -1;
	for (auto i = 0; i < left_min.size(); ++i) {
		max_pos = std::max(max_pos, right_pos[i]);
		if (max_pos >= 0)
			min = std::min(min, left_min[i][max_pos]);
	}
	int result = min;
	min = INT_MAX;
	max_pos = -1;
	for (int i = left_min.size() - 1; i >= 0; --i) {
		max_pos = std::max(max_pos, right_pos[i]);
		if (max_pos >= 0)
			min = std::min(min, left_min[i][max_pos]);
	}
	return std::max(result, min);
}
int shrink_to_bottom(const int top_max_value, const std::vector<std::vector<int>>& top_max, const std::vector<std::vector<int>>& bottom_min) {
	int min = INT_MAX;
	std::vector<int> bottom_pos(top_max.size());
	for (auto i = 0; i < top_max.size(); ++i) {
		bottom_pos[i] = std::distance(top_max[i].begin(), std::upper_bound(top_max[i].begin(), top_max[i].end(), top_max_value));
	}
	int min_pos = bottom_min.front().size();
	for (auto i = 0; i < bottom_min.size(); ++i) {
		min_pos = std::min(min_pos, bottom_pos[i]);
		if (min_pos < bottom_min[i].size())
			min = std::min(min, bottom_min[i][min_pos]);
	}
	int result = min;
	min = INT_MAX;
	min_pos = bottom_min.front().size();
	for (auto i = 1; i <= bottom_min.size(); ++i) {
		min_pos = std::min(min_pos, bottom_pos[bottom_pos.size() - i]);
		if (min_pos < bottom_min[bottom_min.size() - i].size())
			min = std::min(min, bottom_min[bottom_min.size() - i][min_pos]);
	}
	return std::max(result, min);
}
int shrink_to_top(const int bottom_max_value, const std::vector<std::vector<int>>& bottom_max, const std::vector<std::vector<int>>& top_min) {
	int min = INT_MAX;
	std::vector<int> bottom_pos(bottom_max.size());
	for (auto i = 0; i < bottom_max.size(); ++i) {
		bottom_pos[i] = first_less_or_equals(bottom_max[i], bottom_max_value) - 1;
	}
	int max_pos = -1;
	for (auto i = 0; i < top_min.size(); ++i) {
		max_pos = std::max(max_pos, bottom_pos[i]);
		if (max_pos >= 0)
			min = std::min(min, top_min[i][max_pos]);
	}
	int result = min;
	min = INT_MAX;
	max_pos = -1;
	for (int i = top_min.size() - 1; i >= 0; --i) {
		max_pos = std::max(max_pos, bottom_pos[i]);
		if (max_pos >= 0)
			min = std::min(min, top_min[i][max_pos]);
	}
	return std::max(result, min);
}
int cal_max_min(const int max_max_value, const vvi& top_max, const vvi& top_min, const vvi& left_max, const vvi& left_min, const vvi& bottom_max, const vvi& bottom_min, const vvi& right_max, const vvi& right_min) {
	return std::max({
		shrink_to_right(max_max_value, left_max, right_min),
		shrink_to_left(max_max_value, right_max, left_min),
		shrink_to_bottom(max_max_value, top_max, bottom_min),
		shrink_to_top(max_max_value, bottom_max, top_min)
		});
}
int main() {
	int h, w; std::cin >> h >> w;
	std::vector<std::vector<int>> state(h, std::vector<int>(w)); for (auto& line : state) for (auto& area : line) std::cin >> area;
	std::vector<std::vector<int>> flipped(w, std::vector<int>(h));
	for (auto i = 0; i < h; ++i) for (auto j = 0; j < w; ++j) flipped[j][i] = state[i][j];
	auto top_max = flipped;
	auto top_min = flipped;
	auto left_max = state;
	auto left_min = state;
	auto bottom_max = flipped;
	auto bottom_min = flipped;
	auto right_max = state;
	auto right_min = state;
	for (auto i = 0; i < h; ++i) for (auto j = 1; j < w; ++j) {
		left_max[i][j] = std::max(left_max[i][j], left_max[i][j - 1]);
		left_min[i][j] = std::min(left_min[i][j], left_min[i][j - 1]);
		right_max[i][w - j - 1] = std::max(right_max[i][w - j - 1], right_max[i][w - j]);
		right_min[i][w - j - 1] = std::min(right_min[i][w - j - 1], right_min[i][w - j]);
	}
	for (auto i = 1; i < h; ++i) for (auto j = 0; j < w; ++j) {
		top_max[j][i] = std::max(top_max[j][i], top_max[j][i - 1]);
		top_min[j][i] = std::min(top_min[j][i], top_min[j][i - 1]);
		bottom_max[j][h - i - 1] = std::max(bottom_max[j][h - i - 1], bottom_max[j][h - i]);
		bottom_min[j][h - i - 1] = std::min(bottom_min[j][h - i - 1], bottom_min[j][h - i]);
	}
	std::vector<std::pair<int, int>> coordinates; coordinates.reserve(h * w);
	for (auto i = 0; i < h; ++i) for (auto j = 0; j < w; ++j) coordinates.emplace_back(i, j);
	std::sort(coordinates.begin(), coordinates.end(), [&state](const std::pair<int, int>& a, const std::pair<int, int>& b) {return state[a.first][a.second] < state[b.first][b.second]; });
	const int max_value = state[coordinates.back().first][coordinates.back().second];
	const int min_value = state[coordinates.front().first][coordinates.front().second];
	auto min = 0;
	auto max = coordinates.size();
	while (min < max) {
		auto mid = (min + max) / 2;
		auto min_max = state[coordinates[mid].first][coordinates[mid].second];
		auto max_min = cal_max_min(min_max, top_max, top_min, left_max, left_min, bottom_max, bottom_min, right_max, right_min);
		auto min_diff = min_max - min_value;
		auto max_diff = max_value - max_min;
		if (min_diff < max_diff) {
			min = mid + 1;
		}
		else {
			max = mid;
		}
	}
	int result = INT_MAX;
	if (min > 0) {
		int min_max = state[coordinates[min - 1].first][coordinates[min - 1].second];
		result = max_value - cal_max_min(min_max, top_max, top_min, left_max, left_min, bottom_max, bottom_min, right_max, right_min);
	}
	if (min < coordinates.size()) {
		int min_max = state[coordinates[min].first][coordinates[min].second];
		result = std::min(result, min_max - min_value);
	}
	std::cout << result << '\n';
}


Measured memory_bytes: 191048