#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3;
int pre[N+5][N+5];
int get(int u, int v, int x, int y) {
return pre[x][y]-pre[u-1][y]-pre[x][v-1]+pre[u-1][v-1];
}
int rectangle(int n, int m, int h, int w, int a[3001][3001]) {
int l = 1, r = n*m, ans = -1;
while (l <= r) {
int mid = (l+r)/2;
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
pre[x][y] = pre[x-1][y]+pre[x][y-1]-pre[x-1][y-1]+(a[x-1][y-1] <= mid ? 1 : -1);
}
}
bool check = 0;
for (int x = h; x <= n && !check; x++) {
for (int y = w; y <= m && !check; y++) {
if (get(x-h+1, y-w+1, x, y) >= 0) check = 1;
}
}
if (check) {
r = (ans = mid)-1;
}
else {
l = mid+1;
}
}
return ans;
}
