#include <bits/stdc++.h>
#include "quality.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int a[3011][3011],n,m,h,w,pf[3001][3001];
bool check(int x)
{
memset(pf,0,sizeof(pf));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
pf[i][j]=pf[i-1][j]+pf[i][j-1]-pf[i-1][j-1]+(a[i][j]<=x);
}
}
for(int i=h;i<=n;i++)
{
for(int j=w;j<=m;j++)
{
if(pf[i][j]-pf[i-h][j]-pf[i][j-w]+pf[i-h][j-w]>h*w/2)return true;
}
}
return false;
}
int bin()
{
int l=1,r=n*m,mid,ans;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
int rectangle(int r, int c, int H, int W, int q[3001][3001])
{
n=r;
m=c;
h=H;
w=W;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)a[i+1][j+1]=q[i][j];
}
return bin();
}
