Vùng đất xứ Đoài có thể chia thành một lưới ô vuông kích thước ~N \times N~. Tại mỗi vị trí có thể có kho báu hoặc không. Bi định xây nhà tại một vị trí trên vùng đất xứ Đoài. Vào ngày thứ ~i~, anh ấy sẽ đi đào tất cả những kho báu cách vị trí nhà của Bi một khoảng cách ~i - 1~ (Khoảng cách đo bằng khoảng cách Mahattan). Nếu trong một ngày mà Bi đào hơn một kho báu thì anh ấy sẽ được thưởng cuốn bí kíp về các thuật toán.

Cho biết vị trí của các kho báu, hãy giúp Bi tìm vị trí xây nhà để có thể được thưởng cuốn bí kíp về các thuật toán.

Input

Dòng đầu tiên chứa số nguyên ~N~ thỏa ~1 \le N \le 10^3~.

~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên gồm ~0~ hoặc ~1~ (có kho báu).

Output

In ra ma trận ~N \times N~ gồm các số ~0~ hoặc ~1~, trong đó ~1~ là Bi được thưởng bí kíp.

Samples

Sample Input 1

3
1 0 0
0 1 0
0 0 1

Sample Output 1

0 1 1
1 1 1
1 1 0