#include <bits/stdc++.h>
using namespace std;
long long rectangle(int r, int c, int h, int w, int city[3001][3001]) {
// Find min and max values for binary search
int min_val = INT_MAX, max_val = INT_MIN;
for(int i = 0; i < r; i++) {
for(int j = 0; j < c; j++) {
min_val = min(min_val, city[i][j]);
max_val = max(max_val, city[i][j]);
}
}
int window_size = h * w;
int median_pos = (window_size + 1) / 2;
int lo = min_val, hi = max_val;
while(lo < hi) {
int mid = lo + (hi - lo) / 2;
// Build prefix sum array for elements <= mid
int prefix[3002][3002] = {0};
for(int i = 0; i < r; i++) {
for(int j = 0; j < c; j++) {
prefix[i+1][j+1] = prefix[i+1][j] + prefix[i][j+1] - prefix[i][j] +
(city[i][j] <= mid ? 1 : 0);
}
}
// Check all subrectangles
bool possible = false;
for(int i = 0; i <= r-h; i++) {
for(int j = 0; j <= c-w; j++) {
int count = prefix[i+h][j+w] - prefix[i][j+w] - prefix[i+h][j] + prefix[i][j];
if(count >= median_pos) {
possible = true;
break;
}
}
if(possible) break;
}
if(possible) hi = mid;
else lo = mid + 1;
}
return lo;
}
