#include "quality.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int N, M, H, W, A[3001][3001];
int dp[3001][3001];
bool check(int val){
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
dp[i][j] = (A[i][j] < val ? -1 : A[i][j] == val ? 0 : 1);
if (j) dp[i][j] += dp[i][j - 1];
}
}
for (int j = 0; j < M; j++){
for (int i = 1; i < N; i++){
dp[i][j] += dp[i - 1][j];
}
}
/*for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
cout << dp[i][j] << ' ';
}
cout << endl;
}*/
for (int i = H - 1; i < N; i++){
for (int j = W - 1; j < M; j++){
int sum = dp[i][j];
if (i >= H) sum -= dp[i - H][j];
if (j >= W) sum -= dp[i][j - W];
if (i >= H && j >= W) sum += dp[i - H][j - W];
if (sum <= 0) return true;
}
}
return false;
}
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];
int ans = N * M;
int l = 1, r = N * M;
while (l <= r){
int m = (l + r) >> 1;
if (check(m)){
ans = m;
r = m - 1;
} else l = m + 1;
}
return ans;
}
