#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T>
using vec = vector<T>;
using vll = vec<ll>;
using vvll= vec<vll>;
vvll get_pref(vvll &rect, ll med) {
ll n = rect.size(), m = rect[0].size();
vvll out = rect;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(out[i][j] < med) out[i][j] = -1;
else if(out[i][j] > med) out[i][j] = 1;
else out[i][j] = 0;
out[i][j] += (i ? out[i-1][j]:0ll) + (j ? out[i][j-1]:0ll) - (i and j ? out[i-1][j-1]:0ll);
}
}
return out;
}
ll s(ll ti, ll tj, ll bi, ll bj, vvll &pref) {
// cerr << "Sum from (" << ti << "," << tj << ") to (" << bi << "," << bj << "): ";
ll out = pref[bi][bj];
if(ti) out -= pref[ti-1][bj];
if(tj) out -= pref[bi][tj-1];
if(ti and tj) out += pref[ti-1][tj-1];
return out;
}
vvll grid;
int n,m,h,w;
bool check(ll med) {
// cerr << "Checking " << med << endl;
vvll pref = get_pref(grid,med);
for(int i = 0; i <= n-h; i++) {
for(int j = 0; j <= m-w; j++) {
ll sum = s(i,j,i+h-1,j+w-1,pref);
if(sum <= 0) {
// cerr << "YAY! Got it on " << i << " " << j << ", sum " << sum << endl;
return 1;
}
}
}
// cerr << "nope :(" << endl;
return 0;
}
int rectangle(int N, int M, int H, int W, int Q[3001][3001]) {
n = N, m = M, h = H, w = W;
grid.assign(n,vll(m));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
grid[i][j] = Q[i][j];
}
}
int lp = 1, rp = n*m+1;
while(rp - lp > 1) {
int med = (lp+rp)>>1;
if(check(med)) {
// can we do better
rp = med;
} else {
lp = med;
}
}
return rp;
}
