Cho một bảng \(A\) có kích thước \(N \times N\) \((N ∈ \mathbb{N^*})\)

Khoảng cách giữa hai phần tử \(A[i][j]\) và \(A[p][q]\) được định nghĩa là \(|i−p|+|j−q| (1 \leq i,j,p,q \leq N)\).

(Chú ý: \(A[i][j]\) có nghĩa là phần tử ở hàng thứ \(i\) và cột thứ \(j\))

Yêu cầu: Viết chương trình thay thế mỗi phần tử \(0\) trong bảng \(A\) thành phần tử khác \(0\) và gần với nó nhất. Nếu có hai (hoặc nhiều hơn) phần tử khác \(0\) và gần với nó nhất thì giữ nguyên giá trị \(0\).

Input

• Dòng duy nhất chứa số nguyên dương \(N\)
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) phần tử thể hiện giá trị các phần tử trong bảng, biết rằng mỗi phần tử trong bảng là một số nguyên không âm, và không lớn hơn \(10^6\).

Output

• In ra bảng sau khi biến đổi

Example

3
0 0 0
7 0 3
0 5 0 

7 0 3
7 0 3
0 5 0