#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005, maxN = 9e6 + 5;
int n, m, h, w, target;
int a[maxn][maxn], sum[maxn][maxn];
bool ok(int x) {
for (int i=0;i<=n;i++) sum[i][0] = 0;
for (int i=0;i<=m;i++) sum[0][i] = 0;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (a[i][j]<=x);
}
bool ans = false;
for (int i=h;i<=n;i++) for (int j=w;j<=m;j++) {
ans |= (sum[i][j] - sum[i-h][j] - sum[i][j-w] + sum[i-h][j-w] >= target);
}
return ans;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
n = R, m = C, h = H, w = W, target = H*W/2+1;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j] = Q[i-1][j-1];
int l = 1, r = R * C;
while (l<r) {
int mid = (l+r)/2;
if (ok(mid)) r = mid;
else l = mid+1;
}
return l;
}
