Rectangular skating rink

Limits: 3 sec., 256 MiB

This statement was translated automatically from Ukrainian. In case of any discrepancy, the Ukrainian version is authoritative.

The next day, Zenik and Marichka decided to go ice skating.

At the resort, there is a rectangular skating rink of size \(n \times m\). Each of the \(n \times m\) sections of the skating rink has its own danger level \(d_{i j}\).

The skating rink is very large, so the couple does not want to skate over its entire area, but rather choose a square of size \(k \times k\) with sides parallel to the sides of the rink and skate on it.

The danger level of a square is the maximum danger level among all the sections that belong to it.

Marichka asks you to find out what minimum danger level a \(k \times k\) square can have.

Input

The first line contains three integers \(n\), \(m\), and \(k\) — the sizes of the skating rink and the square. The next \(n\) lines each contain \(m\) integers \(d_{i j}\) — the danger level at the corresponding section of the skating rink.

Output

In a single line, output an integer — the minimum danger level of a \(k \times k\) square.

Constraints

\(1 \le n, m \le 1500\), \(1 \le k \le min\{n, m\}\),

\(1 \le d_{i j} \le 10^9\).

10 points: \(n, m \le 100\);

10 points: \(n, m \le 700\);

5 points: no additional constraints.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 3 2 2 5 4 4 1 3 3 2 1	3

Notes

In the example, the possible ways to choose a \(2 \times 2\) square are:

• \(\begin{matrix} 2 & 5 \\ 4 & 1 \end{matrix}\) with a danger level of 5,

• \(\begin{matrix} 5 & 4 \\ 1 & 3 \end{matrix}\) with a danger level of 5,

• \(\begin{matrix} 4 & 1 \\ 3 & 2 \end{matrix}\) with a danger level of 4,

• \(\begin{matrix} 1 & 3 \\ 2 & 1 \end{matrix}\) with a danger level of 3.