#include "quality.h"
#include <iostream>
#define ll long long
using namespace std;
bool ok;
ll ps[3000][3000], l, r, mid, cur;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
l = 1, r = R*C;
while (l < r) {
ok = 0;
mid = (l+r)/2;
for (int i=0; i<R; ++i) {
for (int j=0; j<C; ++j) {
ps[i][j] = (Q[i][j] <= mid ? 1 : 0);
if (i && j) ps[i][j] += ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];
else if (i) ps[i][j] += ps[i-1][j];
else if (j) ps[i][j] += ps[i][j-1];
if (i >= H-1 && j >= W-1) {
cur = ps[i][j];
if (i != H-1 && j != W-1) cur -= ps[i-H][j] + ps[i][j-W] - ps[i-H][j-W];
else if (i != H-1) cur -= ps[i-H][j];
else if (j != W-1) cur -= ps[i][j-W];
if (cur >= (H*W+1)/2) ok = 1;
}
}
}
if (ok) r = mid;
else l = mid+1;
}
return l;
}
