You are given a grid $g$ consisting of $n$ rows each of which is divided into $m$ columns. The grid contains unique values between $1$ and $n times m$ (inclusive).
Also, you are given two values $h$ and $w$, and your task is to find the smallest median value that can be found in a rectangle of size $h times w$.
A rectangle of size $h times w$ is a rectangle consisting of $h$ rows and $w$ columns such that its top left corner is at a cell ($a, thin b$) and its right bottom corner is at a cell ($c, thin d$), and the following conditions are satisfied: ($c -a + 1 equiv h$) and ($d -b + 1 equiv w$).
The median of a set of numbers is the middle element in the sorted list of the given set. For example, the median of ${2, 1, 3}$ is $2$ and the median of ${4, 2, 3, 1, 5}$ is $3$.
The first line contains four integers $n$, $m$, $h$, and $w$ ($1 <= n, thin m <= 10^3$, $1 <= h, thin w <= n$), in which $n$ and $m$ are the number of rows and columns in the grid, respectively, and $h$ and $w$ are representing the size of the required rectangle. Both $h$ and $w$ are odd integers.
Then $n$ lines follow, each line contains $n$ integers, giving the grid. It is guaranteed that the grid contains unique values between $1$ and $n times m$ (inclusive).
Print a single line containing the smallest median value that can be found in a rectangle of size $h times w$.
In the first test case, there are $4$ possible rectangles of size $3 times 3$, which are:
So, the smallest median value that can be found in a rectangle of size $3 times 3$ is $6$.
## Input
The first line contains four integers $n$, $m$, $h$, and $w$ ($1 <= n, thin m <= 10^3$, $1 <= h, thin w <= n$), in which $n$ and $m$ are the number of rows and columns in the grid, respectively, and $h$ and $w$ are representing the size of the required rectangle. Both $h$ and $w$ are odd integers.Then $n$ lines follow, each line contains $n$ integers, giving the grid. It is guaranteed that the grid contains unique values between $1$ and $n times m$ (inclusive).
## Output
Print a single line containing the smallest median value that can be found in a rectangle of size $h times w$.
[samples]
## Note
In the first test case, there are $4$ possible rectangles of size $3 times 3$, which are: Starts at ($1, thin 1$). $arrow.r$ Contains elements: ${13, 16, 15, 5, 2, 8, 14, 11, 12}$. $arrow.r$ Median value = $12$. Starts at ($1, thin 2$). $arrow.r$ Contains elements: ${16, 15, 4, 2, 8, 9, 11, 12, 10}$. $arrow.r$ Median value = $10$. Starts at ($2, thin 1$). $arrow.r$ Contains elements: ${5, 2, 8, 14, 11, 12, 1, 6, 3}$. $arrow.r$ Median value = $6$. Starts at ($2, thin 2$). $arrow.r$ Contains elements: ${2, 8, 9, 11, 12, 10, 6, 3, 7}$. $arrow.r$ Median value = $8$. So, the smallest median value that can be found in a rectangle of size $3 times 3$ is $6$.
**Definitions**
Let $ n, m, h, w \in \mathbb{Z}^+ $ with $ h, w $ odd, $ 1 \leq h \leq n \leq 10^3 $, $ 1 \leq w \leq m \leq 10^3 $.
Let $ G \in \mathbb{Z}^{n \times m} $ be a grid with distinct entries from $ \{1, 2, \dots, nm\} $.
A valid $ h \times w $ rectangle is defined by its top-left corner $ (a, b) $, where $ 1 \leq a \leq n - h + 1 $, $ 1 \leq b \leq m - w + 1 $, and spans rows $ a $ to $ a + h - 1 $ and columns $ b $ to $ b + w - 1 $.
Let $ R_{a,b} \subseteq \mathbb{Z} $ denote the multiset of values in the rectangle starting at $ (a, b) $, with $ |R_{a,b}| = h \cdot w $.
The median of a finite set of size $ h \cdot w $ (odd) is the $ \left( \frac{h \cdot w + 1}{2} \right) $-th smallest element in the sorted version of the set.
**Constraints**
1. $ G $ contains exactly $ nm $ distinct integers from $ 1 $ to $ nm $.
2. $ h $ and $ w $ are odd.
**Objective**
Find
$$
\min_{\substack{1 \leq a \leq n - h + 1 \\ 1 \leq b \leq m - w + 1}} \left( \text{median}(R_{a,b}) \right)
$$