#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
#define ffor(i,o,f) for(int i = o; i < f; i++)
#define bfor(i,f,o) for(int i = f; i >= o; i--)
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define PI acos(-1)
#define endl '\n'
typedef long long ll;
typedef long double ld;
typedef pair < ll, ll > pll;
typedef vector < ll > vll;
const int INF = int(1e9 + 7);
const int MOD = 998244353;
const double EPS = double(1e-9);
const int TAM = 200005;
bool ok(int mid, int q[3001][3001], int r, int c, int h, int w){
vector<vector<int> > aux(r+1, vector<int>(c+1, 0));
ffor(i, 1, r+1){
ffor(j, 1, c+1){
if(q[i-1][j-1] < mid) aux[i][j] = -1;
else if(q[i-1][j-1] == mid) aux[i][j] = 0;
else aux[i][j] = 1;
}
}
ffor(i, 1, r+1){
ffor(j, 1, c+1) aux[i][j] += aux[i-1][j] + aux[i][j-1] - aux[i-1][j-1];
}
ffor(i, h, r+1){
ffor(j, w, c+1){
if(aux[i][j] - aux[i-h][j] - aux[i][j-w] + aux[i-h][j-w] <= 0) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
int n = R*C;
int lo = 1, hi = n, mid, ans = -1;
while(lo <= hi){
mid = (lo+hi) / 2;
if(ok(mid, Q, R, C, H, W)){
ans = mid;
hi = mid - 1;
}
else lo = mid + 1;
}
return ans;
}
