/// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
/// Training ICPC 2024
#include<bits/stdc++.h>
/// #pragma GCC optimize("O3,unroll-loops")
/// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define fi first
#define se second
#define TASK "test"
#define pb push_back
#define EL cout << endl
#define Ti20_ntson int main()
#define in(x) cout << x << endl
#define all(x) (x).begin(),(x).end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define cntbit(x) __builtin_popcount(x)
#define FOR(i,l,r) for (int i = l; i <= r; i++)
#define FORD(i,l,r) for (int i = l; i >= r; i--)
#define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> vii;
typedef unsigned long long ull;
typedef vector<vector<int>> vvi;
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
const int N = 3005;
const int oo = INT_MAX;
const int mod = 1e9 + 7;
const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, a[N][N], m, h, w, pre[N][N];
inline void Read_Input() {
cin >> n >> m >> h >> w;
FOR(i, 1, n)
FOR(j, 1, m)
cin >> a[i][j];
}
int Get(int x, int y, int xx, int yy) {
return pre[xx][yy] - pre[x - 1][yy] - pre[xx][y - 1] + pre[x - 1][y - 1];
}
bool check (int Median) {
FOR(i, 1, n)
FOR(j, 1, m)
if (a[i][j] >= Median)
pre[i][j] = 1;
else pre[i][j] = -1;
/// build prefix_sum 2 chieu
FOR(i, 1, n)
FOR(j, 1, m)
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + pre[i][j];
FOR(i, 1, n - h + 1)
FOR(j, 1, m - w + 1) {
/// o(i, j) = trai tren
int xx = i + h - 1;
int yy = j + w - 1;
if (Get(i, j, xx, yy) > 0) return true;
}
return false;
}
inline void Solve() {
if (h == 1 && w == 1) {
/// toi dang xu li subtask 1
/// if de dam bao rang TH nay chinh xac la subtask 1
int Ans = 0;
FOR(i, 1, n)
FOR(j, 1, m) {
/// o(i, j)
/// a[i][j] chinh xac la trung vi
Ans = max(Ans, a[i][j]);
}
cout << Ans;
return;
}
else if (h == n && w == m) {
/// subtask 2
vector<int> V;
FOR(i, 1, n)
FOR(j, 1, m)
V.push_back(a[i][j]);
sort(V.begin(), V.end());
int sz = V.size();
cout << V[sz / 2];
return;
}
else {
/// subtask cuoi
/// theo khuon mau cua bai B
/// chat nhi phan
int l = 1, r = n * m;
/// thay doi viec lay trung vi
/// tu 1 chieu -> 2 chieu
/// prefixsum 1 chieu - tong cua doan [L, R] >= 0
/// o(x, y) -> o(xx, yy)
/// do do toi thay doi thanh prefix_sum 2 chieu
int Ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
l = mid + 1;
Ans = mid;
}
else r = mid - 1;
}
cout << Ans;
}
}
Ti20_ntson {
// freopen(TASK".INP","r",stdin);
// freopen(TASK".OUT","w",stdout);
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T -- ) {
Read_Input();
Solve();
}
}
Ly8vIEF1dGhvciA6IE5ndXnhu4VuIFRow6FpIFPGoW4gLSBLMTggLSBLSE1UIC0gVUlUCi8vLyBUcmFpbmluZyBJQ1BDIDIwMjQKCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CgovLy8gI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8zLHVucm9sbC1sb29wcyIpCi8vLyAjcHJhZ21hIEdDQyB0YXJnZXQoImF2eDIsYm1pLGJtaTIsbHpjbnQscG9wY250IikKCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBUQVNLICJ0ZXN0IgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIEVMIGNvdXQgPDwgZW5kbAojZGVmaW5lIFRpMjBfbnRzb24gaW50IG1haW4oKQojZGVmaW5lIGluKHgpIGNvdXQgPDwgeCA8PCBlbmRsCiNkZWZpbmUgYWxsKHgpICh4KS5iZWdpbigpLCh4KS5lbmQoKQojZGVmaW5lIGdldGJpdCh4LCBpKSAoKCh4KSA+PiAoaSkpICYgMSkKI2RlZmluZSBjbnRiaXQoeCkgX19idWlsdGluX3BvcGNvdW50KHgpCiNkZWZpbmUgRk9SKGksbCxyKSBmb3IgKGludCBpID0gbDsgaSA8PSByOyBpKyspCiNkZWZpbmUgRk9SRChpLGwscikgZm9yIChpbnQgaSA9IGw7IGkgPj0gcjsgaS0tKQojZGVmaW5lIERlYnVnKGEsbikgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSBjb3V0IDw8IGFbaV0gPDwgIiAiOyBjb3V0IDw8IGVuZGwKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHZpaTsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gdnZpOwppbnQgZmFzdE1heChpbnQgeCwgaW50IHkpIHsgcmV0dXJuICgoKHkteCk+PigzMi0xKSkmKHheeSkpXnk7IH0KCmNvbnN0IGludCBOID0gMzAwNTsKY29uc3QgaW50IG9vID0gSU5UX01BWDsKY29uc3QgaW50IG1vZCA9IDFlOSArIDc7CmNvbnN0IGludCBkNHhbNF0gPSB7LTEsIDAsIDEsIDB9ICwgZDR5WzRdID0gezAsIDEsIDAsIC0xfTsKY29uc3QgaW50IGQ4eFs4XSA9IHstMSwgLTEsIDAsIDEsIDEsIDEsIDAsIC0xfSwgZDh5WzhdID0gezAsIDEsIDEsIDEsIDAsIC0xLCAtMSwgLTF9OwoKaW50IG4sIGFbTl1bTl0sIG0sIGgsIHcsIHByZVtOXVtOXTsKCmlubGluZSB2b2lkIFJlYWRfSW5wdXQoKSB7CiAgICBjaW4gPj4gbiA+PiBtID4+IGggPj4gdzsKICAgIEZPUihpLCAxLCBuKQogICAgICAgIEZPUihqLCAxLCBtKQogICAgICAgICAgICBjaW4gPj4gYVtpXVtqXTsKfQoKaW50IEdldChpbnQgeCwgaW50IHksIGludCB4eCwgaW50IHl5KSB7CiAgICByZXR1cm4gcHJlW3h4XVt5eV0gLSBwcmVbeCAtIDFdW3l5XSAtIHByZVt4eF1beSAtIDFdICsgcHJlW3ggLSAxXVt5IC0gMV07Cn0KCmJvb2wgY2hlY2sgKGludCBNZWRpYW4pIHsKICAgIEZPUihpLCAxLCBuKQogICAgICAgIEZPUihqLCAxLCBtKQogICAgICAgICAgICBpZiAoYVtpXVtqXSA+PSBNZWRpYW4pCiAgICAgICAgICAgICAgICBwcmVbaV1bal0gPSAxOwogICAgICAgICAgICBlbHNlIHByZVtpXVtqXSA9IC0xOwoKICAgIC8vLyBidWlsZCBwcmVmaXhfc3VtIDIgY2hpZXUKCiAgICBGT1IoaSwgMSwgbikKICAgICAgICBGT1IoaiwgMSwgbSkKICAgICAgICAgICAgcHJlW2ldW2pdID0gcHJlW2kgLSAxXVtqXSArIHByZVtpXVtqIC0gMV0gLSBwcmVbaSAtIDFdW2ogLSAxXSArIHByZVtpXVtqXTsKCiAgICBGT1IoaSwgMSwgbiAtIGggKyAxKQogICAgICAgIEZPUihqLCAxLCBtIC0gdyArIDEpIHsKICAgICAgICAgICAgLy8vIG8oaSwgaikgPSB0cmFpIHRyZW4KICAgICAgICAgICAgaW50IHh4ID0gaSArIGggLSAxOwogICAgICAgICAgICBpbnQgeXkgPSBqICsgdyAtIDE7CiAgICAgICAgICAgIGlmIChHZXQoaSwgaiwgeHgsIHl5KSA+IDApIHJldHVybiB0cnVlOwogICAgICAgIH0KICAgIHJldHVybiBmYWxzZTsKfQoKaW5saW5lIHZvaWQgU29sdmUoKSB7CiAgICBpZiAoaCA9PSAxICYmIHcgPT0gMSkgewogICAgICAgIC8vLyB0b2kgZGFuZyB4dSBsaSBzdWJ0YXNrIDEKICAgICAgICAvLy8gaWYgZGUgZGFtIGJhbyByYW5nIFRIIG5heSBjaGluaCB4YWMgbGEgc3VidGFzayAxCgogICAgICAgIGludCBBbnMgPSAwOwogICAgICAgIEZPUihpLCAxLCBuKQogICAgICAgICAgICBGT1IoaiwgMSwgbSkgewogICAgICAgICAgICAgICAgLy8vIG8oaSwgaikKICAgICAgICAgICAgICAgIC8vLyBhW2ldW2pdIGNoaW5oIHhhYyBsYSB0cnVuZyB2aQoKICAgICAgICAgICAgICAgIEFucyA9IG1heChBbnMsIGFbaV1bal0pOwogICAgICAgICAgICB9CiAgICAgICAgY291dCA8PCBBbnM7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgZWxzZSBpZiAoaCA9PSBuICYmIHcgPT0gbSkgewogICAgICAgIC8vLyBzdWJ0YXNrIDIKICAgICAgICB2ZWN0b3I8aW50PiBWOwogICAgICAgIEZPUihpLCAxLCBuKQogICAgICAgICAgICBGT1IoaiwgMSwgbSkKICAgICAgICAgICAgICAgIFYucHVzaF9iYWNrKGFbaV1bal0pOwoKICAgICAgICBzb3J0KFYuYmVnaW4oKSwgVi5lbmQoKSk7CgogICAgICAgIGludCBzeiA9IFYuc2l6ZSgpOwogICAgICAgIGNvdXQgPDwgVltzeiAvIDJdOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGVsc2UgewogICAgICAgIC8vLyBzdWJ0YXNrIGN1b2kKICAgICAgICAvLy8gdGhlbyBraHVvbiBtYXUgY3VhIGJhaSBCCgogICAgICAgIC8vLyBjaGF0IG5oaSBwaGFuCgogICAgICAgIGludCBsID0gMSwgciA9IG4gKiBtOwogICAgICAgIC8vLyB0aGF5IGRvaSB2aWVjIGxheSB0cnVuZyB2aQogICAgICAgIC8vLyB0dSAxIGNoaWV1IC0+IDIgY2hpZXUKICAgICAgICAvLy8gcHJlZml4c3VtIDEgY2hpZXUgIC0gdG9uZyBjdWEgZG9hbiBbTCwgUl0gPj0gMAoKICAgICAgICAvLy8gbyh4LCB5KSAtPiBvKHh4LCB5eSkKCiAgICAgICAgLy8vIGRvIGRvIHRvaSB0aGF5IGRvaSB0aGFuaCBwcmVmaXhfc3VtIDIgY2hpZXUKICAgICAgICBpbnQgQW5zID0gLTE7CgogICAgICAgIHdoaWxlIChsIDw9IHIpIHsKICAgICAgICAgICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgICAgICAgICAgaWYgKGNoZWNrKG1pZCkpIHsKICAgICAgICAgICAgICAgIGwgPSBtaWQgKyAxOwogICAgICAgICAgICAgICAgQW5zID0gbWlkOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgciA9IG1pZCAtIDE7CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgQW5zOwogICAgfQp9CgpUaTIwX250c29uIHsKLy8gICAgZnJlb3BlbihUQVNLIi5JTlAiLCJyIixzdGRpbik7Ci8vICAgIGZyZW9wZW4oVEFTSyIuT1VUIiwidyIsc3Rkb3V0KTsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKDApOyBjb3V0LnRpZSgwKTsKICAgIGludCBUID0gMTsKLy8gICAgY2luID4+IFQ7CiAgICB3aGlsZSAoVCAtLSApIHsKICAgICAgICBSZWFkX0lucHV0KCk7CiAgICAgICAgU29sdmUoKTsKICAgIH0KfQoKCg==