#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <unordered_map>
#include <cstring>
#include <numeric>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#include "quality.h"
using namespace std;
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int q[3001][3001];
int px[3005][3005];
int n,m,h,w;
bool check(int mid) {
memset(px, 0, sizeof(px));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
px[i][j]=px[i-1][j]+px[i][j-1]-px[i-1][j-1]+(q[i][j]<mid);
}
}
for(int i = h; i <= n; i++) {
for(int j = w; j <= m; j++) {
int br = px[i][j]-px[i-h][j]-px[i][j-w]+px[i-h][j-w];
//cout << br << endl;
if(br>(w*h)/2) return 1;
}
}
return 0;
}
int rectangle(int r, int c, int h, int w, int q[3001][3001]) {
for(int i = 1; i <= r; i++) {
for(int j = 1; j <= c; j++) {
::q[i][j]=q[i-1][j-1];
}
}
n=r,m=c,::h=h,::w=w;
int left = 1, right = n*m, mid, ans=-1;
while(left<=right) {
mid=(left+right)/2;
if(check(mid)) {
ans = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
//cout << check(5) << endl;
//for(int i = 1; i <= n*m; i++) cout << check(i);
return ans-1;
}
/*
2 6 1 5
6 1 2 11 7 5
9 3 4 10 12 8
*/
/*
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/
