Description

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

A distance between two elements A_ij and A_pq 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.

Constraints

1 ≤ N ≤ 200, 0 ≤ Ai ≤ 1000000

Input

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

Output

Output must contain N² integers, representing the modified matrix row-by-row.

3
0 0 0
1 0 2
0 3 0

1 0 2
1 0 2
0 3 0

Source

Northeastern Europe 2003, Far-Eastern Subregion