#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int tab[R][C];
vector<int> V;
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
V.push_back(Q[i][j]);
}
}
sort(V.begin(), V.end());
int l=0, r=V.size()-1;
while(l<r){
bool b=0;
int m=(l+r+1)>>1;
int k=V[m];
//cerr<<V[m]<<"\n";
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
tab[i][j]=(Q[i][j]<k);
//cout<<tab[i][j]<<" ";
}
//cout<<"\n";
}
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
if(i)tab[i][j]+=tab[i-1][j];
if(j)tab[i][j]+=tab[i][j-1];
if(i && j)tab[i][j]-=tab[i-1][j-1];
//cout<<tab[i][j]<<" ";
if(i>=H-1 && j>=W-1){
int t=tab[i][j];
if(i>=H)t-=tab[i-H][j];
if(j>=W)t-=tab[i][j-W];
if(i>=H && j>=W)t+=tab[i-H][j-W];
if(t>H*W/2)b=1;
}
}
//cout<<"\n";
}
//cerr<<b<<"\n";
if(b)r=m-1;
else l=m;
}
return V[l];
}
