#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
#define ffor(i,o,f) for(int i = o; i < f; i++)
#define bfor(i,f,o) for(int i = f; i >= o; i--)
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define PI acos(-1)
#define endl '\n'
typedef long long ll;
typedef long double ld;
typedef pair < ll, ll > pll;
typedef vector < ll > vll;
const int INF = int(1e9 + 7);
const int MOD = 998244353;
const double EPS = double(1e-9);
const int TAM = 200005;
bool ok(int mid, vector<vector<int> > rec, int r, int c, int h, int w){
vector<vector<int> > aux(r, vector<int>(c, 0));
ffor(i, 0, r){
ffor(j, 0, c){
if(rec[i][j] < mid) aux[i][j] = -1;
else if(rec[i][j] == mid) aux[i][j] = 0;
else aux[i][j] = 1;
}
}
ffor(i, 1, r) aux[i][0] += aux[i-1][0];
ffor(j, 1, c) aux[0][j] += aux[0][j-1];
ffor(i, 1, r){
ffor(j, 1, c) aux[i][j] += aux[i-1][j] + aux[i][j-1] - aux[i-1][j-1];
}
ffor(i, h, r){
ffor(j, w, c){
if(aux[i][j] - aux[i-1][j] - aux[i][j-1] + aux[i-1][j-1] <= 0) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, vector<vector<int> > rec){
int n = R*C;
int lo = 1, hi = n, mid, ans = -1;
while(lo <= hi){
mid = (lo+hi) / 2;
if(ok(mid, rec, R, C, H, W)){
ans = mid;
hi = mid - 1;
}
else lo = mid + 1;
}
return ans;
}
