Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2437
Nearest number

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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

A distance between two elements Aij and Apq 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^2 integers, representing the matrix row-by-row.


Output

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


This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.


Sample Input

1

3
0 0 0
1 0 2
0 3 0


Sample Output

1 0 2
1 0 2
0 3 0


Source: Northeastern Europe 2003, Far-Eastern Subregion
Submit    Status