The nearest number

Given a matrix A of size N×N, filled with non-negative integers. The distance between the two elements A_ij and A_pq defined as |i-p|+|j-q|. Required to replace each zero element of the nearest non-zero. If there are two or more nearest nonzero cell, zero should be abandoned.

Input

The first line contains the number N (1 ≤ N ≤ 200, 0 ≤ A_ij ≤ 1000000). Then there are N rows of N numbers, separated by spaces that constitute the matrix.

Output

Deduced N rows of N numbers, separated by spaces - modified matrix.

Examples