#include "quality.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 3e3 + 10;
int a[MAXN][MAXN];
int pref[MAXN][MAXN];
int ok[MAXN][MAXN];
int n, m, h, w;
int get_val(int x, int k)
{
if(x < k)
return -1;
else if(x == k)
return 0;
return 1;
}
bool check(int k)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
ok[i][j] = get_val(a[i][j], k);
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + ok[i][j];
}
}
for(int i = h; i <= n; i++)
{
for(int j = w; j <= m; j++)
{
int cur = pref[i][j] - pref[i - h][j] - pref[i][j - w] + pref[i - h][j - w];
if(cur <= 0)
return true;
}
}
return false;
}
int solve()
{
int left = -1;
int right = n * m;
int mid;
while(right - left > 1)
{
mid = left + (right - left) / 2;
if(check(mid))
right = mid;
else
left = mid;
}
return right;
}
int rectangle(int N, int M, int H, int W, int A[3001][3001])
{
n = N;
m = M;
h = H;
w = W;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
a[i][j] = A[i - 1][j - 1];
}
}
return solve();
}
/*
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/
