Nearest number - 2

Interview

Time limit1sMemory limit128 MB

Summary

Replace each zero with the nearest nonzero value using Manhattan distance, but leave zeros that are tied between two or more nearest values unchanged.

Level: Medium5 of 10
Topics: BFS, Graph, Matrix, Implementation
Solved: No attempts yet

Problem

You are given an $N \times N$ matrix $A$ of non-negative integers.

The distance between two elements $A_{i,j}$ and $A_{p,q}$ is defined as $|i - p| + |j - q|$ .

Replace every zero element of the matrix with the value of the nearest non-zero element. If two or more non-zero elements are tied for the minimum distance, leave that zero unchanged.

Input

The first line contains the integer $N$ . It is followed by $N^2$ integers giving the matrix in row-major order.

Output

Print the resulting matrix. Output each row on its own line, with the $N$ integers of a row separated by single spaces.

Constraints

$1 \le N \le 200$ , $0 \le A_{i,j} \le 1000000$

Examples6

Example 1
Input
```
3
0 0 0
1 0 2
0 3 0
```
Expected output
```
1 0 2
1 0 2
0 3 0
```
Example 2
Input
```
1
7
```
Expected output
```
7
```
Example 3
Input
```
1
0
```
Expected output
```
0
```
Example 4
Input
```
3
0 0 0
0 0 0
0 0 0
```
Expected output
```
0 0 0
0 0 0
0 0 0
```
Example 5
Input
```
3
0 0 0
0 5 0
0 0 0
```
Expected output
```
5 5 5
5 5 5
5 5 5
```
Example 6
Input
```
3
5 0 5
0 0 0
0 0 0
```
Expected output
```
5 0 5
5 0 5
5 0 5
```