#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
vector<vector<int>> grid(R+2, vector<int>(C+2));
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) grid[i+1][j+1] = Q[i][j];
}
int lo = 1, hi = R*C;
vector<vector<int>> v(R+2, vector<int>(C+2));
while (lo < hi) {
int mid = (lo+hi)/2;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
if (grid[i][j] < mid) v[i][j] = -1;
else if (grid[i][j] == mid) v[i][j] = 0;
else v[i][j] = 1;
}
}
vector<vector<int>> ps(R+2, vector<int>(C+2));
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) ps[i][j] = v[i][j]+ps[i][j-1];
for (int j = 1; j <= C; j++) ps[i][j] += ps[i-1][j];
}
bool poss = false;
for (int i = H; i <= R; i++) {
for (int j = W; j <= C; j++) {
int sum = ps[i][j]-ps[i-H][j]-ps[i][j-W]+ps[i-H][j-W];
if (sum <= 0) {
poss = true;
break;
}
}
}
if (poss) hi = mid;
else lo = mid+1;
}
return hi;
}
