#include "quality.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
const int MAXN = 300;
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;
int anss, n, m, a[MAXN + 5][MAXN + 5], h, w;
void check()
{
anss = min(anss, *s.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.insert(a[i][j]);
}
check();
ordered_set<int>s1;
for(int i = 0; i < n - h + 1; i++)
{
for(int j = 0; j < w; j++)
s.insert(a[i + h - 1][j]);
for(int j = 0; j < w; j++)
s.erase(a[i - 1][j]);
s1 = s;
check();
for(int j = 1; j < m - w + 1; j++)
{
for(int idx = i; idx <= i + h - 1; idx++)
s.insert(a[idx][j + w - 1]);
for(int idx = i; idx <= i + h - 1; idx++)
{
s.erase(a[idx][j - 1]);
}
check();
}
s = s1;
}
return anss;
}
