#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#include "quality.h"
int ps[3001][3001];
signed char bro(int x, int &R, int &C, int &H, int &W, int Q[3001][3001]) {
FOR(r, R) FOR(c, C) {
ps[r][c] = 0;
if (r > 0) ps[r][c] += ps[r-1][c];
if (c > 0) ps[r][c] += ps[r][c-1];
if (r > 0 && c > 0) ps[r][c] -= ps[r-1][c-1];
ps[r][c] += ((Q[r][c] <= x) ? 1 : -1);
}
for(int r = 0; r + H < R; r++) {
for(int c = 0; c + W < C; c++) {
int res = ps[r+H][c+W];
if (r > 0) res -= ps[r-1][c+W];
if (c > 0) res -= ps[r+H][c-1];
if (r > 0 && c > 0) res += ps[r-1][c-1];
if (res >= 0) return 1;
}
}
return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
H--; W--;
int l = 1, r = R * C + 1;
while(l < r - 1) {
int m = (l + r - 1) / 2;
if (bro(m, R, C, H, W, Q)) r = m + 1;
else l = m + 1;
}
return l;
}
