#include <bits/stdc++.h>
using namespace std;
#include "quality.h"
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int ans=0;
int sum[3001][3001];
//cout<<(H*W)/2;
for(int i=0;i<=R;i++)sum[i][0]=0;
for(int i=0;i<=C;i++)sum[0][i]=0;
for(int step=R*C;step>0;step/=2){
ans+=step;
//cout<<ans<<"\n";
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
sum[i+1][j+1]=sum[i][j+1]+sum[i+1][j]+(Q[i][j]<=ans)-sum[i][j];
//cout<<sum[i+1][j+1]<<" ";
}//cout<<"\n";
}
bool flag=0;
for(int i=H;i<=R;i++){
for(int j=W;j<C;j++){
if(((sum[i][j]-sum[i][j-C]-sum[i-H][j]+sum[i-H][j-C])>((H*W)/2))){
//cout<<ans<<" "<<i<<" "<<j<<"\n";
//cout<<sum[i][j]<<" "<<sum[i][j-C]<<" "<<sum[i-H][j]<<" "<<sum[i-H][j-C]<<"\n"
}
flag=flag||((sum[i][j]-sum[i][j-C]-sum[i-H][j]+sum[i-H][j-C])>((H*W)/2));
}
}
if(flag)ans-=step;
if(step>1)step++;
}
return ans;
}
