/**
* author: namduong93
* created: unknown
* complexity: unknown
**/
#include <bits/stdc++.h>
using namespace std;
#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdo(i, a, b) for (int i = a; i >= b; --i)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define SZ(x) ((int)(x).size())
int get_bit(int x, int i)
{
return x & (1 << i);
}
int turn_bit(int x, int i) { return x | (1 << i); }
int swap_bit(int x, int i) { return x ^ (1 << i); }
typedef pair<int, int> pii;
typedef long long ll;
const int mod = 998244353;
const int N = 3001;
const int inf = 1e9 + 7;
int n;
int R, C, H, W;
int a[N][N], tmp_Q[N][N], sum[N][N];
string str;
stack<int> st;
priority_queue<pii, vector<pii>, greater<pii>> d_heap;
multiset<int> ms;
int find(int m, int Q[3001][3001]) {
fto(i,1,R)
fto(j,1,C) {
if(Q[i][j] == m) tmp_Q[i][j] = 0;
if(Q[i][j] < m) tmp_Q[i][j] = -1;
if(Q[i][j] > m) tmp_Q[i][j] = 1;
}
fto(i,1,R) {
fto(j,1,C) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + tmp_Q[i][j];
}
}
bool exist = false;
fto(i,H,R) fto(j,W,C) {
int guess = sum[i][j] - sum[i - H][j] - sum[i][j - W] + sum[i - H][j - W];
if(guess < 0) return -1;
if (guess == 0) exist = true;
}
if(exist) return 0;
return 1;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
int smaller[R+1][C+1] , bigger[R+1][C+1] , arr[R+1][C+1];
//make grid 1-indexed
memset(smaller , 0 , sizeof(smaller)) ;
memset(bigger , 0 , sizeof(bigger)) ;
for(int i = 1 ; i <= R ; ++i)
{
for(int j = 1 ; j <= C ; ++j)
arr[i][j] = Q[i-1][j-1] ;
}
//make binary search and return minimum answer
int l = 1 , r = R*C , ans = R*C ;
while(l <= r)
{
int mid = (l + r) / 2 ;
//prepare prefix array
for(int i = 1 ; i <= R ; ++i)
{
int s = 0 , b = 0 ;
for(int j = 1 ; j <= C ; ++j)
{
smaller[i][j] = s + smaller[i-1][j];
if(arr[i][j] < mid)
smaller[i][j]++ , ++s;
bigger[i][j] = b + bigger[i-1][j] ;
if(arr[i][j] > mid)
bigger[i][j]++ , ++b;
}
}
//loop on all possible rectangles if size H*W.
bool t = false ;
for(int i = 1 ; i <= R-H+1 ; ++i)
{
for(int j = 1 ; j <= C-W+1 ; ++j)
{
int s = smaller[i+H-1][j+W-1] - smaller[i+H-1][j-1] - smaller[i-1][j+W-1] + smaller[i-1][j-1] ;
int b = bigger[i+H-1][j+W-1] - bigger[i+H-1][j-1] - bigger[i-1][j+W-1] + bigger[i-1][j-1] ;
if(s >= b)
t = true ;
int n = R*C ;
if(s == b && s <= n/2 && b <= n/2)
ans = min(ans , mid) ;
}
}
if(t == true)
r = mid-1 ;
else
l = mid+1 ;
}
return ans ;
}
// void Solve() {
// cin >> R >> C >> H >> W;
// fto(i,1,R) fto(j,1,C) {
// cin>>a[i][j];
// }
// cout<<rectangle(R, C, H, W, a);
// }
// int32_t main()
// {
// if (fopen("test.inp", "r"))
// freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// int Test = 1;
// // cin >> Test;
// fto(iTest, 1, Test)
// {
// Solve();
// }
// // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
// return 0;
// }
