#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;
int rectangle(int r, int c, int h, int w, int Q[3001][3001]){
vector<vector<set<ll>>> calc(r-h+1+5, vector<set<ll>>(c-w+1+5));
vector<vl> erasi(r-h+1+5);
vector<vector<vl>> erasj(r-h+1+5, vector<vl>(c-w+1+5));
ff(i, 0, r-h+1){
ff(j, 0, c-w+1){
if(i == 0 && j == 0){
ff(curi, i, i+h){
ff(curj, j, j+w){
if(curi == i){
erasi[i].pb(Q[curi][curj]);
}
if(curj == j){
erasj[i][j].pb(Q[curi][curj]);
}
calc[i][j].insert(Q[curi][curj]);
}
}
continue;
}
if(j == 0){
set<ll> cur = calc[i-1][j];
ff(curi, 0, erasi[i-1].size()){
cur.erase(erasi[i-1][curi]);
}
ff(curj, j, j+w){
erasi[i].pb(Q[i][curj]);
}
ff(curj, j, j+w){
cur.insert(Q[i+h-1][curj]);
//erasi[i+j-1].pb(Q[i+h-1][])
}
ff(curi, i, i+h){
erasj[i][j].pb(Q[curi][j]);
}
calc[i][j] = cur;
}
else{
set<ll> cur = calc[i][j-1];
for(auto &x : erasj[i][j-1]){
cur.erase(x);
}
ff(curi, i, i+h){
cur.insert(Q[curi][j+w-1]);
}
ff(curi, i, i+h){
erasj[i][j].pb(Q[curi][j]);
}
calc[i][j] = cur;
}
}
}
ll minn = r*c+1;
ff(i, 0, r-h+1){
ff(j, 0, c-w+1){
//cout << i << " " << j << ed;
set<ll> st = calc[i][j];
vl a;
for(auto &p : st){
//cout << p << " ";
a.pb(p);
}
//cout << ed << ed;
ll cur = a[st.size()/2];
minn = min(minn, cur);
}
}
return minn;
}
/*
static int R,C,H,W,Q[3001][3001],i,j,ans;
int main(){
scanf("%d%d%d%d",&R,&C,&H,&W);
for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&Q[i][j]);
ans = rectangle(R,C,H,W,Q);
printf("%d\n",ans);
return 0;
}
*/
