#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int n, int m, int h, int w, int q[3001][3001]) {
int l = 0, r = n * m + 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
vector <vector <int>> pref(n + 1, vector <int>(m + 1, 0));
// cout << mid << endl;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
if (q[i - 1][j - 1] <= mid) {
pref[i][j]--;
}
else {
pref[i][j]++;
}
// cout << pref[i][j] << ' ';
}
// cout << endl;
}
bool pos = 0;
// cout << mid << ": \n";
for (int i = h;i <= n;i++) {
for (int j = w;j <= m;j++) {
int res = pref[i][j] - pref[i - h][j] - pref[i][j - w] + pref[i - h][j - w];
// cout << i << ' ' << j << ": " << res << endl;
if (res <= 0) {
pos = true;
break;
}
}
if (pos) break;
}
if (pos) {
r = mid;
}
else {
l = mid;
}
}
return r;
}
