JZPLIT2 - Turn on the lights 2


Recently Zippy received a puzzle. It is an n*m matrix. In most cells of the matrix, there is a light with a switch. However, some cells do not contain a light with a switch, and they are called "blocks". Once he flips the switch in a cell, lights in visible cells from it(including itself) change to its opposite state (which means: on->off off->on). One cell is visible from another, iff they are in the same row or the same column, and there aren't any blocks between them (and of course the two cells should not be blocks). Zippy wants to turn on all the lights. Please help him to solve the puzzle.

Input

First line, n, m.

The following n lines, each line is a m-length string, represting the original state. (0 means on, 1 means off and 2 means a block)

1<=n,m<=300

number of blocks<=max(n,m)

Output

n lines, each line is a m-length string. It's obvious that if a valid solution exists, there exists a solution that every switch is flipped no more than once. So 1 means the switch is flipped once and 0 means the swtich remains unflipped. Of course, a block do not contain a swtich, so for the cell, you should always output 0. 

It's guaranteed that there always exists a solution. If there are multiple solutions, output any of them. 

Firsline, n, m.
The following n lines, each line is a m-length string, represting the original state. (0 means on, 1 means off and 2 means a block

Example

Input:
2 3
011
121

Output:
001
100


Added by:sevenkplus
Date:2011-09-12
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All