Problem D. Nearest number - 2

Author:A. Klenin   Time limit:5 sec
Input file:input.txt   Memory limit:200 Mb
Output file:output.txt  

Statement

Input is the matrix A of N by N non-negative integers.

A distance between two elements Ai j and Ap q is defined as |i − p| + |j − q|.

Your program must replace each zero element in the matrix with the nearest non-zero one. If there are two or more nearest non-zeroes, the zero must be left in place.

Input file format

Input file contains the number N followed by N2 integers, representing the matrix row-by-row.

Output file format

Output file must contain N2 integers, representing the modified matrix row-by-row.

Constraints

1 ≤ N ≤ 200, 0 ≤ Ai ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
0 0 0
1 0 2
0 3 0
1 0 2
1 0 2
0 3 0

0.063s 0.009s 13