Một trò chơi có tên là Lights Out, luật chơi như sau:

Một bảng đèn hình chữ nhật gồm:

• ~n~ dòng được đánh số ~1..n~
• ~m~ cột được đánh số ~1..m~

Với mỗi một thao tác trên một đèn ~(x; y)~ bất kì, bạn sẽ thay đổi trạng thái của bòng đèn ~(x; y)~ và các bóng đèn khác có chung cạnh với nó.

Yêu cầu: Nhiệm vụ của bạn trong trò chơi này là tắt hết tất cả đèn. Hãy in ra một bảng gồm 1 nếu bạn thao tác trên bóng đèn đó hoặc 0 nếu ngược lại.

Bạn có thể chơi thử tại đây: https://www.logicgamesonline.com/lightsout

Input Specification

• Gồm hai số nguyên dương ~n, m~ - kích thước của bảng ~(m \le 8, n \le 10^4)~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ kí tự 1 nếu đèn ô đó bật hoặc 0 nếu ngược lại.

Output Specification

• In ra một bảng thể hiện thao tác của bạn, 1 nếu bạn thao tác ô đó và 0 ngược lại

Limitations

Note: Dữ liệu đảm bảo luôn có kết quả!

• Subtask 1 [~30\%~]: ~m = 2~
• Subtask 2 [~15\%~]: ~n \times m \le 22~
• Subtask 3 [~55\%~]: Không có giới hạn gì thêm.

Sample Input

6 5
00100
01110
00100
00100
01110
00100

Sample Output

00000
00100
00000
00000
00100
00000