#include "grader.h"
using namespace std;
#define forw(i,l,r) for(int i=l; i<r; i++)
#define fore(i,l,r) for(int i=l; i<=r; i++)
#define forb(i,r,l) for(int i=r; i>=l; i--)
#define rep(i,n) forw(i,0,n)
#define Pi acos(-1.0)
#define mp make_pair
#define ins insert
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define sz(a) (a.size())
#define all(a) a.begin(), a.end()
#define numZeroBitStart(x) (__builtin_clz(x))
#define numZeroBitEnd(x) (__builtin_ctz(x))
#define numOneBit(x) (__builtin_popcount(x))
#define parityOfNumOneBit(x) (__builtin_parity(x))
int rectangle(int r, int c, int h, int w, int a[][3001]){
int left=1, right=r*c, ans=1, b[3001][3001];
while(left<=right){
int med=(left+right)/2;
bool flag=false;
fore(i,1,r) fore(j,1,c){
if(a[i][j]>med) b[i][j]=1;
else if(a[i][j]<med) b[i][j]=-1;
else b[i][j]=0;
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
}
fore(i,1,r-h+1){
if(flag) break;
fore(j,1,c-w+1){
int tot=b[i+h-1][j+w-1]-b[i+h-1][j-1]
-b[i-1][j+w-1]+b[i-1][j-1];
if(tot<=0){
flag=true; break;
}
}
}
if(flag){
ans=med;
right=med-1;
}
else left=med+1;
}
return ans;
}
