#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
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])
{
int r = R, c = C, h = H, w = W;
int k = h * w / 2;
int ans = 1e9;
for (int i = h - 1; i < r; i++)
{
ordered_set<int> s;
for (int a = i - h + 1; a <= i; a++)
{
for (int b = 0; b < w; b++)
{
s.insert(q[a][b]);
}
}
for (int j = w - 1; j < c; j++)
{
auto it = s.find_by_order(k);
ans = min(ans, *it);
if (j == c - 1) break;
for (int z = i - h + 1; z <= i; z++)
{
s.erase(q[z][j - w + 1]);
}
for (int z = i - h + 1; z <= i; z++)
{
s.insert(q[z][j + 1]);
}
}
}
return ans;
}
