#include "quality.h"
#include <bits/stdc++.h>
#define ll long long
ll pref[3001][3001];
int getsum(int i, int j, int h, int w){
return pref[i][j] - pref[i - h][j] - pref[i][j - w] + pref[i - h][j - w];
}
bool f(int med, int n, int m, int h, int w, int a[3001][3001]){
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] + (a[i - 1][j - 1] >= med);
}
}
for(int i = h; i <= n; ++i){
for(int j = w; j <= m; ++j) {
if(getsum(i, j, h, w) >= (h * w + 1) / 2) return 1;
}
}
return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int l = 0, r = R * C + 1;
while(l + 1 < r){
int mid = (l + r) / 2;
if(f(mid, R, C, H, W, Q)) l = mid;
else r = mid;
}
return l;
}
