#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 3e3 + 1;
int f[lim][lim];
int rectangle(int n, int m, int H, int W, int Q[3001][3001]){
memset(f, 0, sizeof(f));
int low = 1, high = n * m, ans;
while(low <= high){
int mid = (low + high) >> 1;
for(int i = 1; i <= n; i++){
for(int j = 1, s = 0; j <= m; j++){
f[i][j] = (s += (Q[i - 1][j - 1] > mid ? -1 : 1)) + f[i - 1][j];
}
}
bool flag = false;
for(int i = H; i <= n; i++){
for(int j = W; j <= m; j++){
if(f[i][j] - f[i][j - W] - f[i - H][j] + f[i - H][j - W] > 0){
flag = true;
i = n;
break;
}
}
}
if(flag){
high = (ans = mid) - 1;
}
else{
low = mid + 1;
}
}
return ans;
}
