#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int maxn=3005;
int n,m,h,w;
int a[maxn][maxn];
ordered_set s;
void rem_x(int x,int start,int finish)
{
for(int j=start;j<=finish;j++)
s.erase(s.find(a[x][j]));
}
void add_x(int x,int start,int finish)
{
for(int j=start;j<=finish;j++)
s.insert(a[x][j]);
}
void rem_y(int y,int start,int finish)
{
for(int i=start;i<=finish;i++)
s.erase(s.find(a[i][y]));
}
void add_y(int y,int start,int finish)
{
for(int i=start;i<=finish;i++)
s.insert(a[i][y]);
}
int median()
{
int sz=s.size();
/*for(int i : s)
cout<<i<<' ';
cout<<endl;*/
int ret=*(s.find_by_order(sz/2));
//cout<<ret<<endl;
return ret;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
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-1;i++)
{
for(int j=0;j<w;j++)
s.insert(a[i][j]);
}
int ans=n*m;
for(int i=0;i+h-1<n;i++)
{
if(i%2==0)
add_x(i+h-1,0,w-1);
else
add_x(i+h-1,m-w,m-1);
ans=min(ans,median());
if(i%2==0)
{
rem_y(0,i,i+h-1);
for(int j=w;j<m;j++)
{
add_y(j,i,i+h-1);
ans=min(ans,median());
rem_y(j-w+1,i,i+h-1);
}
}
else
{
rem_y(m-1,i,i+h-1);
for(int j=m-w-1;j>=0;j--)
{
add_y(j,i,i+h-1);
ans=min(ans,median());
rem_y(j+w-1,i,i+h-1);
}
}
if(i%2==0)
add_y(m-w,i,i+h-1);
else
add_y(w-1,i,i+h-1);
if(i%2==0)
rem_x(i,m-w,m-1);
else
rem_x(i,0,w-1);
}
return ans;
}
