#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
void print(multiset<int> x){
for(auto i:x) cout<<i<<" ";
cout<<endl;
}
int A,B;
void addcolumn(vector<vector<int>> &q, multiset <int> &s, int c, int sq, int eq){
assert(eq<=A);
for(int i=sq;i<eq;i++) s.insert(q[i][c]);
}
void removecolumn(vector<vector<int>> &q,multiset <int> &s, int c, int sq, int eq){
assert(eq<=A);
for(int i=sq;i<eq;i++){
s.erase(s.lower_bound(q[i][c]));
}
}
void addrow(vector<vector<int>> &q, multiset <int> &s, int r, int sq, int eq){
assert(eq<=B);
for(int i=sq;i<eq;i++) s.insert(q[r][i]);
}
void removerow(vector<vector<int>> &q, multiset <int> &s, int r, int sq, int eq){
assert(eq<=B);
for(int i=sq;i<eq;i++){
s.erase(s.lower_bound(q[r][i]));
}
}
int getmed(multiset<int>&s){
int l = *(s.begin()), r = *(s.rbegin());
while(r-l>1){
int m = (l+r)/2;
if( distance(s.begin(),s.lower_bound(m)) >(s.size()/2)) r = m;
else l = m;
}
return l;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
vector<vector<int>> q(R,vector<int>(C)); A=R, B=C;
for(int i=0;i<R;i++)
for(int j=0;j<C;j++)
q[i][j]=Q[i][j];
multiset<int> s;
int ans = INT_MAX;
for(int i=0;i<H;i++)
for(int j=0;j<W;j++)
s.insert(q[i][j]);
for(int i=0;i<=R-H;i++){
if(!(i%2)){
for(int j=1;j<=C-W;j++){
ans = min(ans, getmed(s));
removecolumn(q,s,j-1,i,i+H);
addcolumn(q,s,j+W-1,i,i+H);
}
ans = min(ans,getmed(s));
removerow(q,s,i,C-W,C);
if(i+H<R)addrow(q,s,i+H,C-W,C);
}else{
for(int j=C-W-1;j>=0;j--){
ans = min(ans, getmed(s));
removecolumn(q,s,j+W,i,i+H);
addcolumn(q,s,j,i,i+H);
}
ans = min(ans,getmed(s));
removerow(q,s,i,0,W);
if(i+H<R) addrow(q,s,i+H,0,W);
}
}
return ans;
}
