#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int qs[3001][3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int l = 1, r = R*C, mid;
int medcnt = H*W/2+1;
while(l <= r) {
mid = (l+r) >> 1;
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
qs[i+1][j+1] = (Q[i][j] <= mid);
qs[i+1][j+1] += qs[i+1][j] + qs[i][j+1] - qs[i][j];
}
}
int cnt = 0;
for(int i=0;i+H<=R;i++) {
for(int j=0;j+W<=C;j++) {
cnt = max(cnt, qs[i+H][j+W] - qs[i+H][j] - qs[i][j+W] + qs[i][j]);
}
}
if(cnt >= medcnt) r = mid-1;
else l = mid+1;
}
return l;
}
