Найближче число

Задано матрицю A розміром N×N, заповнену невід'ємними цілими числами. Відстань між двома елементами A_ij і A_pq визначена як |i-p|+|j-q|. Потрібно замінити кожен нульовий елемент матриці найближчим ненульовим. Якщо є дві або більше найближчих ненульових комірки, нуль повинен бути залишеним.

Вхідні дані

У першому рядку міститься число N (1 ≤ N ≤ 200, 0 ≤ A_ij ≤ 1000000). Далі йде N рядків по N чисел, відокремлених пропусками і які являють собою матрицю.

Вихідні дані

Виводиться N рядків по N чисел, відокремлених пропусками, - модифікована матриця.

Приклади