#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 rectangle(int r, int c, int h, int w, int q[3001][3001]) {
ordered_set<int> s;
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
s.insert(q[i][j]);
}
}
int ans=2e9;
int j = w-1;
for(int i = h-1; i < r-1; i++) {
if(j==w-1) {
for(; j < c-1; j++) {
ans=min(ans, *s.find_by_order(h*w/2));
for(int k = i-h+1; k <= i; k++) {
s.erase(q[k][j-w+1]);
}
for(int k = i-h+1; k <= i; k++) {
s.insert(q[k][j+1]);
}
}
ans=min(ans, *s.find_by_order(h*w/2));
}
else {
for(; j >= w; j--) {
ans=min(ans, *s.find_by_order(h*w/2));
for(int k = i-h+1; k <= i; k++) {
s.erase(q[k][j]);
}
for(int k = i-h+1; k <= i; k++) {
s.insert(q[k][j-w]);
}
}
ans=min(ans, *s.find_by_order(h*w/2));
}
for(int k = j-w+1; k <= j; k++) {
s.erase(q[i-h+1][j]);
}
for(int k = j-w+1; k <= j; k++) {
s.insert(q[i+1][j]);
}
ans=min(ans, *s.find_by_order(h*w/2));
}
return ans;
}
/*
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
*/
