#include "quality.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<vector<int>> a;
int R,C,H,W;
int f(int x){
vector<vector<int>> pref(R, vector<int>(C,0));
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if(a[i][j]<x) pref[i][j]--;
if(a[i][j]>x) pref[i][j]++;
if(i>0) pref[i][j]+=pref[i-1][j];
if(j>0) pref[i][j]+=pref[i][j-1];
if(j>0&&i>0) pref[i][j]-=pref[i-1][j-1];
//cerr << pref[i][j] << " ";
}
//cerr << "\n";
}
int mn=1;
for (int i = H-1; i < R; i++)
{
for (int j = W-1; j < C; j++)
{
int sm=pref[i][j];
if(i>=H) sm-=pref[i-H][j];
if(j>=W) sm-=pref[i][j-W];
if(i>=H&&j>=W) sm+=pref[i-H][j-W];
if(sm<0) sm=-1;
else sm=min(1,sm);
mn=min(sm,mn);
}
}
return mn;
}
int rectangle(int _R, int _C, int _H, int _W, int Q[3001][3001]) {
R=_R;
C=_C;
H=_H;
W=_W;
a.resize(R, vector<int>(C));
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
a[i][j]=Q[i][j];
}
}
int l=1; int r=R*C;
while(l<r){
int mid=(l+r)/2;
int ff=f(mid);
if(ff==0){
l=mid;
break;
}else if(ff<0) {
r=mid;
}else{
l=mid+1;
}
}
return l;
}
