#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 10;
int s[MAXN][MAXN];
bool in(int x, int y, int R, int C){
return x >= 0 && x < R && y >= 0 && y < C;
}
bool check(int R, int C, int H, int W, int Q[3001][3001], int x){
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
s[i][j] = (Q[i][j] <= x);
if(i > 0) s[i][j] += s[i - 1][j];
if(j > 0) s[i][j] += s[i][j - 1];
if(i > 0 && j > 0) s[i][j] -= s[i - 1][j - 1];
}
}
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
int x_1 = i, y_1 = j, x_2 = i + H - 1, y_2 = j + W - 1;
if(in(x_1, y_1, R, C) && in(x_1, y_2, R, C) && in(x_2, y_1, R, C) && in(x_2, y_2, R, C)){
int sum = s[x_2][y_2];
if(x_1 > 0) sum -= s[x_1 - 1][y_2];
if(y_1 > 0) sum -= s[x_2][y_1 - 1];
if(x_1 > 0 && y_1 > 0) sum += s[x_1 - 1][y_1 - 1];
if(sum >= (H * W + 1) / 2) return true;
}
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
int l = 1, r = R * C;
while(l < r){
int m = l + (r - l) / 2;
if(check(R, C, H, W, Q, m)) r = m;
else l = m + 1;
}
return r;
}
