#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
const int MAXN = 3001;
int rectangle(int n,int m,int H,int W, int Q[MAXN][MAXN]){
vector<vector<int>> pre(n+1,vector<int>(m+1,0));
vector<vector<int>> grid(n+1,vector<int>(m+1,0));
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
grid[i+1][j+1] = Q[i][j];
}
}
int l=1, r = n * m;
int res = r;
function<bool(int)> check = [&] (int mid) -> bool {
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + (grid[i][j] <= mid ? 1 : -1);
}
}
for (int i=H;i<=n;i++){
for (int j=W;j<=m;j++){
int val = pre[i][j] - pre[i-H][j] - pre[i][j-W] + pre[i-H][j-W];
if (val>0) return true;
}
}
return false;
};
while (l<=r){
int mid = (l+r)>>1;
if (check(mid)){
res = mid;
r=mid-1;
} else{
l = mid + 1;
}
}
return res;
}
