Alice has just created an $N\times M$-pixel drawing on a digital art program. Each pixel can be coloured in one of ${10}^9$ different colours, numbered from $1$ to ${10}^9$, or it can be blank, in which case it will be numbered with $0$.

After Alice finished the drawing, she decided that it would look better if the edges of the drawing were expanded by $K$ pixels, maintaining colour. More specifically, let a step be a move of one pixel directly up, down, left, or right. If a blank pixel is $K$ or fewer steps away from a coloured pixel, it should take on the colour of that pixel. If multiple pixels are $K$ or fewer steps away, choose the colour of the closest one, and if multiple pixels are equally close, choose the lowest-numbered colour among them.

Please help Alice do this!

Constraints

$1\le N,M,K\le 1500$

$0\le c_{i,j}\le {10}^9$

Subtask 1 [2/15]

$1\le N,M,K\le 50$

Subtask 2 [2/15]

$1\le N,M,K\le 400$

$0\le c_{i,j}\le 1$

Subtask 3 [3/15]

$1\le N,M,K\le 400$

Subtask 4 [3/15]

$0\le c_{i,j}\le 1$

Subtask 5 [5/15]

No additional constraints.

Input Specification

The first line contains three space-separated integers, $N$, $M$, and $K$.
The next $N$ lines each contain $M$ space-separated integers: the colour $c_{i,j}$ of each pixel.

Output Specification

Output $N$ lines, each containing $M$ space-separated integers: the drawing after being expanded by $K$ pixels.

Sample Input

3 10 1
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 2 2 2 0 0
0 0 0 0 0 0 0 0 0 0

Sample Output

0 0 1 1 1 2 2 2 0 0
0 1 1 1 1 2 2 2 2 0
0 0 1 1 1 2 2 2 0 0