Với đồ thị ~G = (V, E)~ ta xây dựng đồ thị mới ~G' = (E, V')~ cũng gồm các đỉnh của ~V~ nhưng các cạnh thì được xây dựng như sau:

Giữa hai đỉnh ~u, v~ của ~G'~ có cạnh nối ~⇔~ có đường đi từ ~u~ đến ~v~ trong ~G~. Đồ thị ~G' = (E, V')~ gọi là bao đóng của đồ thị ~G = (V, E)~.

Bài toán:Cho đơn đồ thị ~G(V, E)~ có ~n~ đỉnh được biểu diễn vởi ma trận kề ~A=(a_{ij})~. Hãy tìm bao đóng của ~G(V, E)~.

Input

• Dòng đầu chứa số nguyên ~n~ là số đỉnh của đồ thị ~G~;
• ~n~ dòng tiếp theo, dòng thứ ghi ~n~ số nguyên ~0~ hoặc ~1~ là dòng ~i~ của ma trận kề ~A~.

Giới hạn:

• ~1 ≤ n ≤ 1000~.

Output

• Ghi ra ma trận kề ~A’~ của đồ thị ~G’ = (E, V’)~.

Sample

Input #1

5
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
0 0 0 1 0

Output #1

0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

Problem source: Chuyên Sơn La Online Judge