#ifndef LOCAL
#include "quality.h"
#endif
#include <bits/stdc++.h>
using namespace std;
int harita[3001][3001], r, c, h, w;
bool check(int m){
vector<vector<int>> prefix(r + 1, vector<int>(c + 1, 0));
for (int i = 1; i <= r; i++){
for (int o = 1; o <= c; o++){
if (harita[i - 1][o - 1] <= m)
prefix[i][o] += 1;
prefix[i][o] += prefix[i - 1][o];
prefix[i][o] += prefix[i][o - 1];
prefix[i][o] -= prefix[i - 1][o - 1];
}
}
for (int i = 0; i <= r - h; i++){
for (int o = 0; o <= c - w; o++){
if (prefix[i + h][o + w] - prefix[i][o + w] - prefix[i + h][o] + prefix[i][o] >= (w * h + 1) / 2){
return true;
}
}
}
return false;
}
int divandq(int tl, int tr){
if (tl == tr)
return tl;
int m = (tl + tr) >> 1;
if (check(m)){
return divandq(tl, m);
}else{
return divandq(m + 1, tr);
}
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
for (int i = 0; i < R; i++){
for (int o = 0; o < C; o++){
harita[i][o] = Q[i][o];
}
}
r = R;
c = C;
h = H;
w = W;
return divandq((H * W + 1) >> 1, R * C / 2 + 1);
}
