#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int pf[3001][3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
int l = 1, r = R * C, ans = -1;
while(l <= r){
int md = (l + r) / 2;
memset(pf, 0, sizeof pf);
for(int i = 0;i<R;i++){
for(int j = 0;j<C;j++){
pf[i + 1][j + 1] = pf[i][j + 1] + pf[i + 1][j] - pf[i][j] + (Q[i][j] < md);
}
}
bool f = 0;
for(int i = 0;i + H<=R && !f;i++){
for(int j = 0;j + W<=C;j++){
if(pf[i + H][j + W] - pf[i][j + W] - pf[i + H][j] + pf[i][j] >= (H * W) / 2){
f = 1;
break;
}
}
}
if(f){
ans = md;
r = md - 1;
}else{
l = md + 1;
}
}
return ans + 1;
}
