#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define mp make_pair
#define fi first
#define se second
#include "grader.h"
///#include "quality.h"
using namespace std;
typedef pair<int, int> pii;
const int lim = 3e3;
int st[lim * lim * 4 + 2];
int pfm[lim + 2][lim + 2];
pii pos[lim * lim + 2];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
forn(i, 0, R - 1){
forn(j, 0, C - 1){
pos[Q[i][j]] = mp(i + 1, j + 1);
}
}
int mitadtot = (H * W) / 2;
int li = 1, ls = R * C, mitad, res;
bool bandera = 0, bandera1;
int suma;
while(li <= ls){
mitad = (li + ls) / 2;
forn(i, 0, R - 1){
forn(j, 0, C - 1){
pfm[i + 1][j + 1] = (Q[i][j] < mitad) ? 1 : 0;
pfm[i + 1][j + 1] += pfm[i + 1][j] + pfm[i][j + 1] - pfm[i][j];
}
}
///cout << mitad << "\n";
forn(i, 1, R){
forn(j, 1, C){
///cout << pfm[i][j] << " ";
}
///cout << "\n";
}
bandera = 0;
bandera1 = 0;
forn(i, H, R){
forn(j, W, C){
suma = pfm[i][j] - pfm[i - H][j] - pfm[i][j - W] + pfm[i - H][j - W];
///cout << i << " " << j << " " << suma << " ";
if(suma > mitadtot){
bandera1 = 1;
}
if(suma == mitadtot){
if((pos[mitad].fi > i - H && pos[mitad].fi <= i) && (pos[mitad].se > j - W && pos[mitad].se <= j)){
bandera = 1;
}
}
}
///cout << "\n";
}
if(bandera1){
ls = mitad - 1;
}
else if(!bandera){
li = mitad + 1;
}
else{
res = mitad;
break;
}
}
return res;
}
