#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#include "quality.h"
int N, M, blockh, blockw;
int A[3010][3010], ss[3010][3010];
int query(int x1, int y1, int x2, int y2) {
return ss[x2][y2] - ss[x1 - 1][y2] - ss[x2][y1 - 1] + ss[x1 - 1][y1 - 1];
}
int good(int x) {
memset(ss, 0, sizeof ss);
for (int i = 1; i <= N; ++i) for (int j = 1; j <= M; ++j) {
ss[i][j] = ss[i - 1][j] + ss[i][j - 1] - ss[i - 1][j - 1] + (A[i][j] > x);
}
for (int i = blockh; i <= N; ++i) for (int j = blockw; j <= M; ++j) {
int val = query(i - blockh + 1, j - blockw + 1, i, j);
if (val <= blockh * blockw / 2) return 1;
}
return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
N = R, M = C, blockh = H, blockw = W;
int lo = 0, hi = R * C + 1;
for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) A[i + 1][j + 1] = Q[i][j];
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (good(mid)) hi = mid;
else lo = mid;
}
return hi;
}
