#include "quality.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using db=double;
using sll=__int128;
using lb=long double;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
#define int long long
int r=R; int c=C; int h=H; int w=W;
vector<vector<int>>a(r+1,vector<int>(c+1));
for(int i=1; i<=r; i++){
for(int j=1; j<=c; j++){
a[i][j]=Q[i-1][j-1];
}
}
int left=1; int right=r*c;
while(left<right){
int mid=(left+right)>>1; vector<vector<int>>v(r+1,vector<int>(c+1)); vector<vector<int>>prefix(r+1,vector<int>(c+1));
for(int i=1; i<=r; i++){
for(int j=1; j<=c; j++){
v[i][j]=(a[i][j]<=mid); prefix[i][j]=v[i][j]+prefix[i][j-1]+prefix[i-1][j]-prefix[i-1][j-1];
}
}
int mx=0;
for(int i=1; i+h-1<=r; i++){
for(int j=1; j+w-1<=c; j++){
int x1=i; int y1=j; int x2=i+h-1; int y2=j+w-1;
mx=max(mx,prefix[x2][y2]-prefix[x2][y1-1]-prefix[x1-1][y2]+prefix[x1-1][y1-1]);
}
}
if(mx>=(h*w)/2+1)right=mid; else left=mid+1;
}
#undef int
return (int)left;
}
