Giải bài trực tuyến

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 x 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 ≤ M, N ≤ 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.

Example

Input:
4 4
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1

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