#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
const int maxn=3005;
int n,m,h,w;
int a[maxn][maxn];
vector<int>sorta;
struct fenwick
{
int n;
vector<int>bit;
void init(int N)
{
n=N;
bit.assign(n+1,0);
}
void add(int idx, int val)
{
for(++idx; idx <= n; idx += idx & -idx)
bit[idx] += val;
}
int sum(int idx)
{
int s=0;
for(++idx; idx > 0; idx -= idx & -idx)
s += bit[idx];
return s;
}
int kth(int k)
{
int curr=0,acc=0;
for(int i=(1<<30);i>0;i/=2)
{
if(curr+i<=n && acc+bit[curr+i]<=k)
{
curr+=i;
acc+=bit[curr];
}
}
return curr;
}
} tree;
inline void rem_x(int x,int start,int finish)
{
for(int j=start;j<=finish;j++)
tree.add(a[x][j],-1);
}
inline void add_x(int x,int start,int finish)
{
for(int j=start;j<=finish;j++)
tree.add(a[x][j],1);
}
inline void rem_y(int y,int start,int finish)
{
for(int i=start;i<=finish;i++)
tree.add(a[i][y],-1);
}
inline void add_y(int y,int start,int finish)
{
for(int i=start;i<=finish;i++)
tree.add(a[i][y],1);
}
int median()
{
int sz=h*w;
int idx=tree.kth(sz/2);
return sorta[idx];
}
int newidx(int curr)
{
return lower_bound(sorta.begin(),sorta.end(),curr)-sorta.begin();
}
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];
sorta.push_back(a[i][j]);
}
}
sort(sorta.begin(),sorta.end());
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
a[i][j]=newidx(a[i][j]);
}
}
tree.init(n*m);
for(int i=0;i<h-1;i++)
{
for(int j=0;j<w;j++)
tree.add(a[i][j],1);
}
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;
}
