#include <bits/stdc++.h>
#include "quality.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
int ps[3001][3001];
int rectangle(int n, int m, int h, int w, int Q[3001][3001]) {
int lo = 1, hi = n*m;
while (lo < hi) {
int mid = (lo + hi) / 2;
memset(ps, 0, sizeof ps);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ps[i+1][j+1] = ps[i][j+1] + ps[i+1][j] - ps[i][j] + (Q[i][j] <= mid);
}
}
int ok = 0;
for (int i = h; i <= n; i++) {
for (int j = w; j <= m; j++) {
if (ps[i][j] - ps[i-h][j] - ps[i][j-w] + ps[i-h][j-w] > h*w/2) ok = 1;
}
}
if (ok) hi = mid;
else lo = mid+1;
}
return lo;
}
/*
static int R,C,H,W,Q[3001][3001],i,j,ans;
int main(){
scanf("%d%d%d%d",&R,&C,&H,&W);
for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&Q[i][j]);
ans = rectangle(R,C,H,W,Q);
printf("%d\n",ans);
return 0;
}*/
