You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Sân nhà Tâm được lát bằng $m\times n$ viên gạch hình vuông ($m,n>1$), thành dạng lưới ô vuông $m$ dòng, $n$ cột như Hình 1. Tọa độ của viên gạch ở dòng $i$, cột $j$ là $(i,j)$.

Tâm kêu chú chó nhà mình đi từ $(1,1)$ tới $(m,n)$ với yêu cầu:

• Từ một viên gạch, chú chó chỉ có thể bước đi sang viên gạch có cùng cạnh (Hình 2 biểu diễn ví dụ về bước đi hợp lệ).
• Đường đi phải là ngắn nhất (trên ít viên gạch nhất) có thể.

Tâm đã từng huấn luyện chú chó phản ứng theo một cách cụ thể với ánh sáng; vì vậy, Tâm đã dễ dàng điều khiển chú chó đi theo đúng yêu cầu của mình. Trên đường đi, chú chó để lại dấu chân trên từng viên gạch. Tuy nhiên, có đúng một viên trong số đó không có dấu chân chó.

Yêu cầu

Từ dấu chân chó trên những viên gạch, hãy tái hiện đầy đủ đường đi của chú chó.

Dữ liệu

Vào từ đầu vào chuẩn

• Dòng đầu tiên chứa 2 số nguyên $m$ và $n$.
• $m$ dòng tiếp theo, mỗi dòng chứa $n$ số 0 hoặc 1. Số thứ $j$ của dòng $i$ bằng 1 nếu viên $(i,j)$ có dấu chân chó, bằng 0 nếu ngược lại.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra đầu ra chuẩn $m$ dòng, mỗi dòng chứa $n$ số 0 hoặc 1. Số thứ $j$ của dòng $i$ bằng 1 nếu viên $(i,j)$ có thể nằm trên đường đi của chú chó, bằng 0 nếu ngược lại. Các số trên cùng một dòng cách nhau bởi dấu cách.

Lưu ý, diễn đạt “viên $(i,j)$ có thể nằm trên đường đi của chú chó” mang hàm ý: Nếu có nhiều đường đi (theo đúng yêu cầu của Tâm) cùng để lại dấu chân đã biết, thì phải xét tất cả những đường đi đó, xem viên $(i,j)$ có nằm trên ít nhất một trong số chúng hay không.

Ví dụ mẫu

7 5
1 0 0 0 0
1 1 0 0 0
0 0 0 0 0
0 1 0 0 0
0 1 1 1 0
0 0 0 1 0
0 0 0 1 1

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

2 3
1 1 0
0 1 0

1 1 0
0 1 1

Giới hạn

Subtask 1 (100% số điểm): $m,n\le3\times{10}^3;m\times n\le3\times{10}^6$.