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 1\,500~

~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