Description

FJ knows that cows with higher IQ produce more milk, so he prepared a tile-flipping puzzle for them.

On an $M \times N$ grid ($1 \leq M, N \leq 15$), each cell has a tile that can be flipped. One side of a tile is black, the other side is white. Flipping a tile toggles its color between black and white.

However, the cows are clumsy: when they flip the tile in a cell, all tiles that share an edge with it also flip.

Now they want to know the minimum number of flips needed to make all tiles face white up.

Input Format

The first line contains two integers $M, N$.

Then follow $M$ lines, each with $N$ integers, describing the initial state: $0$ means white side up, $1$ means black side up.

Output Format

If it is impossible to make all tiles white side up, output IMPOSSIBLE.

Otherwise, output $M$ lines, each with $N$ integers; the number at row $i$, column $j$ denotes how many times the tile at row $i$, column $j$ is flipped.

Your output must have the minimum total number of flips. If there are multiple solutions, output the lexicographically smallest one.

Here, lexicographically smallest means the string formed by removing all whitespace from your output is lexicographically smallest.

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

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

Hint

The following solution also has the minimum number of operations, but it is not lexicographically smallest.

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

Translated by ChatGPT 5