#include<bits/stdc++.h>
#include "quality.h"
#define ll long long
#define pb push_back
using namespace std;
int h , w , r , c , grid[3001][3001] , pref[3001][3001];
void reset(){
for(int i = 0 ; i <= r ; i++){
for(int j = 0 ; j <= c ; j++){
pref[i][j] = 0;
}
}
}
bool inside(int x , int y){
return 0 < x && x <= r && 0 < y && y <= c;
}
int rectangle(int R , int C , int H , int W , int Q[3001][3001]){
r = R; c = C; h = H; w = W;
for(int i = 1 ; i <= r ; i++){
for(int j = 1 ; j <= c ; j++){
grid[i][j] = Q[i - 1][j - 1];
}
}
int lef = 0 , rig = r * c , ans = 0;
while(lef <= rig){
int mid = (lef + rig) / 2;
reset();
for(int i = 1 ; i <= r ; i++){
for(int j = 1 ; j <= c ; j++){
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + (grid[i][j] <= mid);
}
}
bool bs = false;
for(int i = 1 ; i <= r ; i++){
for(int j = 1 ; j <= c ; j++){
int x = i , y = j , x0 = x + h - 1 , y0 = y + w - 1;
if(inside(x0 , y0)){
int tt = pref[x0][y0] - pref[x - 1][y0] - pref[x0][y - 1] + pref[x - 1][y - 1];
//cout << x << " " << y << " " << x0 << " " << y0 << " " << pref[x0][y0] << " " << pref[x][y0] << " " << pref[x0][y] << " " << pref[x][y] << endl;
if(tt > (h * w) / 2) bs = true;
}
}
}
if(bs){
ans = mid;
rig = mid - 1;
}
else{
lef = mid + 1;
}
}
return ans;
}
