#include "quality.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
const int MAXN = 3000;
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>;
ordered_set<int>s[MAXN + 5];
int anss, n, m, a[MAXN + 5][MAXN + 5], h, w;
void check(ordered_set<int>ss)
{
anss = min(anss, *ss.find_by_order((h * w) / 2));
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
anss = 1e9;
n = R; m = C; h = H; w = W;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)a[i][j] = Q[i][j];
for(int i = 0; i < h; i++)
{
for(int j = 0; j < w; j++)
s[0].insert(a[i][j]);
}
check(s[0]);
for(int i = 1; i < n - h + 1; i++)
{
s[i] = s[i - 1];
for(int j = 0; j < w; j++)
s[i].insert(a[i + h - 1][j]);
for(int j = 0; j < w; j++)
s[i].erase(a[i - 1][j]);
check(s[i]);
}
for(int i = 0; i <= n - h + 1; i++)
{
for(int j = 1; j <= m - w + 1; j++)
{
for(int idx = i; idx <= i + h - 1; idx++)
s[i].insert(a[idx][j + w - 1]);
for(int idx = i; idx <= i + h - 1; idx++)
{
s[i].erase(a[idx][j - 1]);
}
check(s[i]);
}
}
return anss;
}
