#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int NMAX = 3000;
vector <int> v;
int rectangle(int n, int m, int r, int c, int q[NMAX + 1][NMAX + 1]) {
int ans = n * m + 1;
int mid = (r * c + 1) / 2;
for(int lin = 0; lin < n - r + 1; lin++) {
for(int col = 0; col < m - c + 1; col++) {
v.clear();
for(int i = lin; i <= lin + r - 1; i++)
for(int j = col; j <= col + c - 1; j++)
v.push_back(q[i][j]);
nth_element(v.begin(), v.begin() + mid - 1, v.end());
ans = min(ans, v[mid - 1]);
//cout << lin << " " << col << " " << v[mid - 1] << '\n';
}
}
return ans;
}
