#include "quality.h"
using namespace std;
const int maxn = 3e3+10;
int n, m, hh, ww, mat[maxn][maxn], b[maxn][maxn], sum[maxn][maxn];
bool check(int x){
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(mat[i][j] > x) b[i][j] = 1;
else if(mat[i][j] == x) b[i][j] = 0;
else b[i][j] = -1;
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
sum[i][j] = b[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
if(i>=hh and j >= ww and (sum[i][j] - sum[i-hh][j] - sum[i][j-ww] + sum[i-hh][j-ww]) <= 0) return true;
}
}
return false;
}
int rectangle(int r, int c, int h, int w, int a[3001][3001]) {
n = r, m = c, hh = h, ww = w;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
mat[i][j] = a[i-1][j-1];
}
}
int ini = 1, fim = n*m, meio, ans = -1;
while(ini <= fim){
meio = (ini + fim) >> 1;
if(check(meio)){
fim = meio - 1;
ans = meio;
}
else{
ini = meio + 1;
}
}
return ans;
}
