#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3007;
const int INF = 1e9+7;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int mt[R+1][C+1];
for(int i = 0; i <= R; i++)
for(int j = 0; j <= C; j++)
mt[i][j] = 0;
for(int i = 1; i <= R; i++){
for(int j = 1; j <= C; j++){
mt[i][j] = Q[i-1][j-1] + mt[i-1][j] + mt[i][j-1] - mt[i-1][j-1];
}
}
int mn = INF;
int xi, yj;
for(int i = 0; i < R-H+1; i++){
for(int j = 0; j < C-W+1; j++){
int sm = mt[i+H][j+W] - mt[i][j+W] - mt[i+H][j] + mt[i][j];
if(sm < mn){
xi = i, yj = j;
mn = sm;
}
}
}
int mm = (H*W)/2;
vector<int> vi;
for(int i = xi; i < xi+H; i++){
for(int j = yj; j < yj+W; j++){
vi.push_back(Q[i][j]);
}
}
sort(vi.begin(), vi.end());
return vi[mm];
}
