#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int sum[3005][3005];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int st=0,en=1e7,ans=0;
while(st<=en){
int m=(st+en)/2;
for(int i=1;i<=R;i++)for(int j=1;j<=C;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
sum[i][j]+=(Q[i-1][j-1]<=m);
}
int can=0;
for(int i=H;i<=R;i++)for(int j=W;j<=C;j++){
int temp=sum[i][j]-sum[i-H][j]-sum[i][j-W]+sum[i-H][j-W];
if(temp>H*W/2)can=1;
}
if(can){
ans=m;
en=m-1;
}else{
st=m+1;
}
}
//cerr<<"work\n";
return ans;
}
