Rectangular skating rink

Limits: 3 sec., 256 MiB

This statement was translated automatically from Ukrainian.

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.