Quality of Living

Interview

Time limit5sMemory limit256 MB

Summary

Find the smallest median among all H by W subrectangles of a grid holding the numbers 1 to R times C.

Level: Medium6 of 10
Topics: Binary search, Prefix sum, Matrix
Solved: No attempts yet

Problem

The city of Alberta is laid out as a rectangular grid of blocks. Rows are numbered from $0$ in the north to $R-1$ in the south, and columns from $0$ in the west to $C-1$ in the east.

The quality of living of each block is written as one distinct integer between $1$ and $R \times C$ , called its quality rank. The block with quality rank $1$ has the best quality of living, and the block with quality rank $R \times C$ has the worst.

Hongjun looks only at $H \times W$ regions that fit entirely inside the grid. $H$ and $W$ are odd, and $1 \le H \le R$ , $1 \le W \le C$ . For an odd number of quality ranks, the median $m$ is the value that has as many better ranks as worse ranks.

Every $H \times W$ region has one median quality rank. Write a program that finds the best of those medians, that is, the smallest one.

Input

The first line contains the integers $R$ , $C$ , $H$ , $W$ , separated by spaces. $R$ and $C$ are the number of rows and columns of the city, and $H$ and $W$ are the number of rows and columns of the region Hongjun picked. $H$ and $W$ are odd, with $1 \le H \le R$ and $1 \le W \le C$ .

Each of the next $R$ lines contains $C$ integers. The $j$ -th number on the $i$ -th line is the quality rank of the block in row $i-1$ and column $j-1$ . The $R \times C$ numbers on the grid are the integers from $1$ to $R \times C$ , each appearing exactly once.

Output

Print the smallest median over all $H \times W$ regions on the first line.

Examples4

Example 1

Input

5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15

Expected output

Example 2
Input
```
1 1 1 1
1
```
Expected output
```
1
```
Example 3
Input
```
3 3 3 3
7 2 3
9 1 8
4 5 6
```
Expected output
```
5
```

Example 4

Input

5 5 1 1
11 6 7 13 10
12 16 14 8 24
1 22 20 18 2
9 25 17 15 23
4 3 5 19 21

Expected output