#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int lo=0,hi=1e9;
while(hi>=lo){
int mid= (hi+lo)/2;
vector< vector< int> > ps(R+1, vector<int> (C+1));
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
if(Q[i][j]>mid)ps[i+1][j+1]=-1;
else if (Q[i][j]<mid)ps[i+1][j+1]=1;
}
}
for(int i=1;i<=R;i++){
for(int j=1;j<=H;j++){
// ps[i][j]+= ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1];
}
}
int mx=-1e9;
for(int i=1;i<=R-H+1;i++){
for(int j=1;j<=C-W+1;j++){
vector<int>v;
int s=0;
for(int y=0;y<H;y++){
for(int x=0;x<W;x++){
s+=(ps[i+y][j+x]);
}
}
mx=max(mx,s);
}
}
if(mx>=0){
hi=mid-1;
}
else{
lo=mid+1;
}
}
return lo;
}
