#include <bits/stdc++.h>
using namespace std;
#include "quality.h"
const int LIM = 3000;
int g[LIM+1][LIM+1];
int rectangle(int r, int c, int h, int w, int q[LIM+1][LIM+1]){
int low = 1, high = r*c;
while(low < high){
int mid = (low + high) / 2;
bool ok = 0;
for(int i=0; i<r; ++i){
for(int j=0; j<c; ++j){
g[i+1][j+1] = q[i][j] <= mid ? 1 : -1;
g[i+1][j+1] += g[i][j+1] + g[i+1][j] - g[i][j];
if(i+1>=h && j+1>=w && g[i+1][j+1] - g[i+1-h][j+1-w] +
g[i+1-h][j+1] - g[i+1][j+1-w] > 0) ok = 1;
}
}
if(ok) high = mid;
else low = mid + 1;
}
return low;
}
