#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
const int maxn=3005;
int n,m,h,w;
int a[maxn][maxn];
int pos[maxn][maxn];
int pref[maxn][maxn];
bool check(int curr)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]>curr)
pos[i+1][j+1]=1;
else
pos[i+1][j+1]=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]+pos[i][j];
}
}
int sum;
for(int i=h;i<=n;i++)
{
for(int j=w;j<=m;j++)
{
sum=pref[i][j]-pref[i-h][j]-pref[i][j-w]+pref[i-h][j-w];
if(sum<=(h*w)/2)
return true;
}
}
return false;
}
int bin_search()
{
int l=1,r=n*m,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid))
r=mid-1;
else
l=mid+1;
}
return l;
}
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<n;i++)
{
for(int j=0;j<m;j++)
a[i][j] = Q[i][j];
}
return bin_search();
}
