#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxn = 5 + 5e5, mod = 7 + 1e9, INF = 1e9;
int n, m, h, w, pref[3001][3001];
bool check(int median_val, int arr[3001][3001]) {
memset(pref, 0, sizeof(pref));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
if (arr[i - 1][j - 1] <= median_val)
pref[i][j]++;
}
for (int i = h; i <= n; i++)
for (int j = w; j <= m; j++) {
int cnt =
pref[i][j] - pref[i - h][j] - pref[i][j - w] + pref[i - h][j - w];
if (cnt > h * w / 2)
return 1;
}
return 0;
}
int rectangle(int r, int c, int _h, int _w, int q[3001][3001]) {
n = r, m = c;
h = _h, w = _w;
int left = 0, right = r * c, ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid, q)) {
right = mid - 1;
ans = mid;
} else
left = mid + 1;
}
return ans;
}
