#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
#define pi pair<int,int>
int rectangle(int r, int c, int h, int w, int d[3001][3001]) {
int ans = 100000000;
set<int> s;
for (int ii=0; ii<h; ii++) {
for (int jj=0; jj<w; jj++) {
s.insert(d[ii][jj]);
}
}
queue<pair<pi, set<int>>> q;
q.push({{0,0}, s});
vector<vector<bool>> vst(r, vector<bool>(c, false));
vst[0][0] = true;
auto it = s.begin();
advance(it, s.size()/2);
int med = *it;
ans = min(ans, med);
int di[2] = {0, 1}, dj[2] = {1, 0};
while (!q.empty()) {
pair<pi, set<int>> cur = q.front(); q.pop();
int ci=cur.first.first, cj=cur.first.second;
for (int e=0; e<2; e++) {
int ni=ci+di[e], nj=cj+dj[e];
if (ni>=h || nj>=w || vst[ni][nj]) continue;
vst[ni][nj] = true;
set<int> ns = cur.second;
if (e==0) {
for (int i=0; i<h; i++) ns.erase(d[ci+i][cj]);
for (int i=0; i<h; i++) ns.insert(d[ci+i][cj+w]);
}
else {
for (int j=0; j<w; j++) ns.erase(d[ci][cj+j]);
for (int j=0; j<w; j++) ns.insert(d[ci+h][cj+j]);
}
auto it = ns.begin();
advance(it, ns.size()/2);
int med = *it;
ans = min(ans, med);
//cout<< med<< ' '<< ni<< ' '<< nj<<'\n';
// for (auto &x : ns) cout<< x<< ' ';
// cout<< '\n'<< '\n';
q.push({{ni,nj}, ns});
}
}
return ans;
}
