#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#include "quality.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;
int pom[3001][3001];
bool moze(int a,int R,int C,int H,int W,int** Q){
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
pom[i][j]=(Q[i][j]<=a);
if(i>0) pom[i][j]+=pom[i-1][j];
if(j>0) pom[i][j]+=pom[i][j-1];
if(i>0 && j>0) pom[i][j]-=pom[i-1][j-1];
}
}
for(int i=H-1;i<R;i++){
for(int j=W-1;j<C;j++){
int sta=0;
sta+=pom[i][j];
if(i>H-1) sta-=pom[i-H][j];
if(j>W-1) sta-=pom[i][j-W];
if(i>H-1 && j>W-1) sta+=pom[i-H][j-W];
if(sta>=W*H/2+1) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int ret=-1;
int** novoQ=new int*[3001];
for(int i=0;i<=3000;i++){
novoQ[i]=new int[3001];
}
for(int i=0;i<=3000;i++){
for(int j=0;j<3000;j++) novoQ[i][j]=Q[i][j];
}
int l=1;
int r=R*C;
while(l<=r){
int mid=l+(r-l)/2;
if(moze(mid,R,C,H,W,novoQ)){
ret=mid;
r=mid-1;
}else{
l=mid+1;
}
}
return ret;
}
