Centre for Gifted Education - Hanoi university of Technology

Sau khi bị mất cây đèn thần vào tay tên phù thuỷ. Lâu đài và nàng công chúa vợ Aladin cũng bị tên phù thuỷ làm phép cho biến mất. May mắn cho Aladin vẫn còn sự giúp đỡ của thần nhẫn.

Để có thể bắt kịp tên phù thuỷ, cách duy nhất là Aladin ngồi trên tấm thảm bay, nhưng tấm thảm đã bị tên phù thuỷ cướp mất. Thần nhẫn hoá phép ra 1 bản vẽ của tấm thảm bay. Tấm thảm bay chỉ có 2 màu đen hoặc trắng. Để có được tấm thảm bay. Aladin phải may tấm thảm theo bản vẽ của thần nhẫn:

Tấm thảm là 1 hình vuông gồm N dòng và N cột tạo thành N × N ô vuông đơn vị. Các ô vuông đơn vị có màu đen hoặc trắng.

Với mỗi hình vuông có độ dài cạnh bằng 2, quy định trước số ô màu đen phải có.

Aladin rất cần may 1 tấm thảm có yêu cầu như trên, vì thế anh ta đã dùng phéo thuật của thần nhẫn dịch chuyển đến tương lai và nhờ sự giúp đỡ của các bạn.

Input

Dòng đầu ghi số nguyên N (2 <= n <= 200)

N – 1 dòng sau, mỗi dòng ghi N – 1 số trong phạm vi 0..4.

Số thứ j của dòng thứ i trong N – 1 dòng trên là số ô đen trong hình vuông gồm 4 ô (i,j), (i+1,j), (i,j+1), (i+1,j+1).

Output

Gồm N dòng, mỗi dòng ghi N số 0 hoặc 1 tương ứng với ô đó không màu trắng hoặc màu đen. Nếu có nhiều kết quả thỏa mãn bạn chỉ cần đưa ra một kết quả.

Example

Input:
4
3 2 3
2 3 3
1 2 1

Output:
1 1 0 1
1 0 1 1
0 1 1 0
0 0 0 0