Nhà sherry có ~1~ khu vườn rất rộng và trồng nhiều loại cây. Để đón tết năm ~2010~ sherry sẽ trồng thật nhiều mai và đào. Và chỉ có mai và đào mà thôi.

Khu vườn nhà sherry có dạng hình chữ nhật, kích thước ~M \times N~. Trên đó có ~1~ số ô được đánh dấu để trồng cây. Để tăng tính thẩm mỹ của khu vườn sherry muốn số cây mai và đào trong khu vườn chênh lệch nhau không quá ~1~. Đồng thời số cây mai, đào trên mỗi hàng, cột của khu vườn cũng chênh lệch nhau không quá ~1~.

Input

Dòng ~1~: ghi ~2~ số nguyên ~M~, ~N~ ~(1 \leq M~, ~N \leq 250)~

~M~ dòng tiếp theo: Mỗi dòng ghi ~N~ số, trong đó số thứ ~j~ của hàng thứ ~i~ bằng ~1/0~ tương ứng với ô ~(i~, ~j)~ có/không trồng cây.

Output

Gồm ~M~ dòng: Mỗi dòng ghi ~N~ số nguyên, các ô không trồng cây ghi ra ~0~, các ô trồng cây có giá trị ~1/2~ tương ứng ở đó trồng mai/đào.

Sample Input

4 4
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1

Sample Output

2 0 1 0 
0 2 0 1 
1 0 2 0 
0 1 0 2