#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int Q[3001][3001];
int rectangle(int R, int C, int H, int W, int tmp[3001][3001]) {
auto can = [&](int x) {
for(int it = 0; it < 3; it++)
for(int i = 0; i < R; i++)
for(int j = 0; j < C; j++) {
if(it == 0) Q[i][j] = tmp[i][j] >= x ? -1 : 1;
if(it == 1 && i) Q[i][j] += Q[i-1][j];
if(it == 2 && j) Q[i][j] += Q[i][j-1];
}
for(int i = H-1; i < R; i++)
for(int j = W-1; j < C; j++) {
int res = Q[i][j];
if(i-H>=0) res -= Q[i-H][j];
if(j-W>=0) res -= Q[i][j-W];
if(i-H>=0&&j-W>=0) res += Q[i-H][j-W];
//cout << i << " " << j << " " << res << endl;
if(res > 0) return 1;
}
return 0;
};
int ans = -1;
for(int i = 1<<30; i>>=1;)
ans += i*!can(ans+i);
return ans;
}
