#include "quality.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
using namespace std;
int n,m;
const int maxn=3010;
int pref[maxn][maxn],q[maxn][maxn];
bool check(int x,int w,int h)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(q[i][j]<=x)
{
pref[i][j]=1;
}else 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]+pref[i][j];
if(w<=j&&h<=i&&pref[i][j]-pref[i-h][j]-pref[i][j-w]+pref[i-h][j-w]>w*h/2)
{
return 1;
}
}
}
return 0;
}
int rectangle(int r, int c, int h, int w, int Q[3001][3001])
{
int minc=1e9;
n=r;
int ans=0;
m=c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)q[i][j]=Q[i-1][j-1];
}
int l=1,r1=n*m+100;
while(l<=r1)
{
int m=(l+r1)/2;
if(check(m,w,h))
{
ans=m;
r1=m-1;
}else l=m+1;
}
return ans;
}
