#include "quality.h"
#include<iostream>
const int MAXN = 3024;
int q[MAXN][MAXN];
int pref[MAXN][MAXN];
int n, m, h, w;
using namespace std;
bool check(int x)
{
//cout<<x<<'#'<<endl;
for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)pref[i][j]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
if(q[i][j]<=x)
{
pref[i][j]++;
}
//cout<<pref[i][j]<<' ';
}
//cout<<endl;
}
for(int i=h;i<=n;i++)
{
for(int j=w;j<=m;j++)
{
int cnt=pref[i][j]-pref[i-h][j]-pref[i][j-w]+pref[i-h][j-w];
if(cnt>=((h*w)/2+1))return true;
}
}
return false;
}
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=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
q[i][j]=Q[i-1][j-1];
//cout<<q[i][j]<<' ';
}
//cout<<endl;
}
int l=1;
int r=n*m;
int ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
return ans;
}
