#include <bits/stdc++.h>
// #include "grader.cpp"
#include "quality.h"
using namespace std;
#define cin(vec) for(auto& i : vec) cin >> i
#define cout(vec) for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b) for (int i = a; i < b; i++)
#define F first
#define S second
#define pb(n) push_back(n)
#define pf(n) push_front(n)
#define dci(d) fixed<<setprecision(d)
#define sp ' '
#define el '\n'
#define all(v) v.begin(),v.end()
int pref[3002][3002];
int sub(int i,int j,int k,int l){
return pref[k][l]-pref[k][j-1]-pref[i-1][l]+pref[i-1][j-1];
}
int rectangle(int n, int m, int r, int c, int a[3001][3001]) {
int left=1,right=n*m,ans=1e9;
map<int,pair<int,int>>ch;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ch[a[i][j]]={i,j};
}
}
while(left<=right){
int mid=(left+right)/2;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i&&j)
pref[i][j]=a[i-1][j-1]<mid;
else
pref[i][j]=0;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
pref[i+1][j+1]+=pref[i+1][j];
}
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=m;j++){
// cout<<pref[i][j]<<' ';
// }cout<<el;
// }cout<<el;
for(int j=0;j<m;j++){
for(int i=0;i<n;i++){
pref[i+1][j+1]+=pref[i][j+1];
}
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=m;j++){
// cout<<pref[i][j]<<' ';
// }cout<<el;
// }cout<<el;
int dec=0;
for(int i=0;i<=n-r;i++){
for(int j=0;j<=m-c;j++){
int num=(ch[mid].F>=i&&ch[mid].F<=(i+r-1)&&ch[mid].S>=j&&ch[mid].S<=(j+c-1));
int x=sub(i+1,j+1,i+r,j+c);
if(x>=r*c-x-num){
dec=1;
if(x==r*c-x-num){
// cout<<i<<' '<<j<<' '<<i+r-1<<' '<<j+c-1<<' '<<x<<' '<<mid<<el<<el;
ans=min(ans,mid);
}
}
}
}
// cout<<dec<<el;
if(dec)
right=mid-1;
else
left=mid+1;
}
return ans;
}
