#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
const int N=3010;
int a[N][N];
int pref[N][N];
int n,m,w,h;
int range(int l1,int r1,int l2,int r2){
return pref[l2][r2]-pref[l1-1][r2]-pref[l2][r1-1]+pref[l1-1][r1-1];
}
bool check(int x){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
pref[i][j]=0;
pref[i][j]=pref[i][j-1]+pref[i-1][j]-pref[i-1][j-1];
if(a[i][j]>x){
pref[i][j]++;
}
else if(a[i][j]==x){
}
else{
pref[i][j]--;
}
}
}
for(int i=1;i<=n-w+1;++i){
for(int j=1;j<=m-h+1;++j){
if(range(i,j,i+w-1,j+h-1)<=0){
return 1;
}
}
}
return 0;
}
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){
a[i][j]=q[i][j];
}
}
int l=1;
int r=n*m;
int answ;
while(l<=r){
int m=(l+r)/2;
if(check(m)){
r=m-1;
answ=m;
}
else{
l=m+1;
}
}
return answ;
}
