#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
const int maxn = 3e3 + 5;
int prefsum[maxn][maxn];
int grid[maxn][maxn];
int r, c, h, w;
bool check(int x){
memset(prefsum, 0, sizeof(prefsum));
prefsum[0][0]= grid[0][0] <=x ? 1: -1;
for(int i =1; i<r; i++){
prefsum[i][0] = grid[i][0] <= x ? 1: -1;
prefsum[i][0] +=prefsum[i-1][0] ;
}
for(int j =1; j<c; j++){
prefsum[0][j] = grid[0][j] <= x ? 1: -1;
prefsum[0][j] +=prefsum[0][j-1] ;
}
for(int i = 1;i < r; i++){
for(int j = 1; j< c;j++){
prefsum[i][j] = grid[i][j]<= x ? 1: -1;
prefsum[i][j] += prefsum[i-1][j] + prefsum[i][j-1] - prefsum[i-1][j-1];
}
}
/*if(x == 9){
for(int i = 0;i < r; i++){
for(int j = 0; j< c;j++){
cout << prefsum[i][j]<<" ";
}
cout <<endl;
}
}*/
for(int top = 0; top <= r- h; top++){
for(int left = 0; left <= c-w; left++ ){
int val = prefsum[top + h -1] [left + w - 1];
if(top > 0)
val -= prefsum[top -1][left + w -1];
if(left > 0)
val -= prefsum[top + h -1][left - 1];
if( top > 0 and left > 0)
val += prefsum[top -1][left - 1];
if(val > 0)
return true;
}
}
return false;
}
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 =0; i<r; i++)
for(int j =0; j<c; j++)
grid[i][j] = Q[i][j];
int left = 1;
int right = C * R;
while(left != right){
int mid = (left + right)/ 2;
//cout << mid <<": "<<check(mid)<<endl;
if(check(mid)){
right = mid;
}
else{
left = mid + 1;
}
}
return left;
}
/***********/
