#include "quality.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
int ans = INT_MAX, med, n, m;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int n = R, m = C, med = H*W/2, ans = INT_MAX;
indexed_set c;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
c.insert({Q[i][j], i*C+j});
}
}
pair<int, int> p = *c.find_by_order(med);
ans = min(ans, p.first);
for (int i2 = H; i2 < R; i2++) {
int i1 = i2-H;
for (int j = 0; j < W; j++) {
c.erase({Q[i1][j], i1*C+j});
}
for (int j = 0; j < W; j++) {
c.insert({Q[i2][j], i2*C+j});
}
p = *c.find_by_order(med);
ans = min(ans, p.first);
}
bool f = 1;
int co = 0;
for (int j1 = 1; j1 < m; j1++) {
int j2 = j1+W-1;
if (j2 >= m) {
break;
}
//cout << co++ << endl;
if (f) {
for (int i = R-1; i >= R-H; i--) {
c.erase({Q[i][j1-1], i*C+j1-1});
c.insert({Q[i][j2], i*C+j2});
}
for (int i2 = R-1; i2 >= 0; i2--) {
int i1 = i2-H;
if (i1 < 0) {
break;
}
for (int j = j1; j <= j2; j++) {
c.erase({Q[i2][j], i2*C+j});
}
for (int j = j1; j <= j2; j++) {
c.insert({Q[i1][j], i1*C+j});
}
p = *c.find_by_order(med);
ans = min(ans, p.first);
}
} else {
for (int i = 0; i < H; i++) {
c.erase({Q[i][j1-1], i*C+j1-1});
c.insert({Q[i][j2], i*C+j2});
}
for (int i2 = H; i2 < R; i2++) {
int i1 = i2-H;
for (int j = j1; j <= j2; j++) {
c.erase({Q[i1][j], i1*C+j});
}
for (int j = j1; j <= j2; j++) {
c.insert({Q[i2][j], i2*C+j});
}
p = *c.find_by_order(med);
ans = min(ans, p.first);
}
}
f ^= 1;
}
return ans;
}
