#include <bits/stdc++.h>
using namespace std;
long long rectangle(int r, int c, int h, int w, int city[3001][3001])
{
long long best = LLONG_MAX;
int window_size = h * w;
int median_pos = (window_size + 1) / 2 - 1;
// For each starting row
for(int i = 0; i <= r-h; i++) {
// Use multiset to maintain sorted window values
multiset<int> window;
// Initialize first window of this row
for(int k = 0; k < h; k++) {
for(int m = 0; m < w; m++) {
window.insert(city[i+k][m]);
}
}
// Get median of first window
auto it = window.begin();
advance(it, median_pos);
best = min(best, (long long)*it);
// Slide window horizontally
for(int j = 1; j <= c-w; j++) {
// Remove leftmost column
for(int k = 0; k < h; k++) {
window.erase(window.find(city[i+k][j-1]));
}
// Add rightmost column
for(int k = 0; k < h; k++) {
window.insert(city[i+k][j+w-1]);
}
// Get new median
it = window.begin();
advance(it, median_pos);
best = min(best, (long long)*it);
}
}
return best;
}
