#include <bits/stdc++.h>
using namespace std;
int R, C, H, W, A[3005][3005];
int dp[3005][3005];
int query(int i1, int j1, int i2, int j2) {
return dp[i2][j2] - dp[i2][j1 - 1] - dp[i1 - 1][j2] + dp[i1 - 1][j1 - 1];
}
bool solve(int X) {
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
dp[i][j] = (A[i][j] < X ? 1 : -1);
if (A[i][j] == X) dp[i][j] = 0;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + dp[i][j];
}
}
for (int i = 1; i + H - 1 <= R; i++) {
for (int j = 1; j + W - 1 <= C; j++) {
if (query(i, j, i + H - 1, j + W - 1) >= 0) return true;
}
}
return false;
}
int rectangle(int r, int c, int h, int w, int q[3001][3001]) {
R = r;
C = c;
H = h;
W = w;
///*
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
A[i][j] = q[i - 1][j - 1];
}
}//*/
int left = 1, right = R * C;
int ans = 1e9;
///*
while (left <= right) {
int mid = (left + right) >> 1;
if (solve(mid)) {
right = mid - 1;
ans = min(ans, mid);
} else {
left = mid + 1;
}
}//*/
return ans;
}
