cho.sh

Problem

Sungji is secretly playing a bungeoppang tycoon game. This version has a special rule.

The board is an M by N grid, and each cell contains one bungeoppang. Each one is either front side up or back side up. When you press a cell, the bungeoppang in that cell and the bungeoppang in the four orthogonally adjacent cells are flipped at the same time. Cells outside the grid are ignored.

All bungeoppang can be taken out only when their front sides are facing up. Find a way to press as few cells as possible so that every bungeoppang is front side up.

Input

The first line contains two integers M and N, the number of rows and columns of the grid. (1 ≤ M ≤ 15, 1 ≤ N ≤ 15)

Each of the next M lines contains N integers, each either 0 or 1. A 0 means the bungeoppang is currently front side up, and a 1 means it is currently back side up.

Output

If it is possible to make every bungeoppang front side up, print M lines with N numbers each. For each cell, print 1 if you press it and 0 otherwise.

The printed plan must use the minimum possible number of pressed cells. If several minimum plans exist, print the lexicographically smallest one when read row by row from top to bottom and left to right within each row.

If no plan exists, print IMPOSSIBLE.

Hint

If you first press (2, 1), the board becomes:

Then pressing (2, 4) gives:

Then pressing (3, 1) gives:

Finally, pressing (3, 4) makes every cell 0.

The following plan is also possible, but it is lexicographically later, so it is not the output.

Bungeoppang Tycoon

Problem

Input

Output

Hint