#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<=C;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++){
int s=0;
int x1=i,x2=i+H-1;
int y1=j,y2=j+W-1;
mx=max(mx,ps[x2][y2]+ps[x1-1][y1-1]-ps[x1-1][y2]-ps[x2][y1-1]);
}
}
if(mx>=0){
hi=mid-1;
}
else{
lo=mid+1;
}
}
return lo;
}
