Problem D: PIPI的方格Ⅱ

Problem D: PIPI的方格Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 256  Solved: 74
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一个n*m的01矩阵。每次操作PIPI都可以任选一个格子使其翻转(即0->1或1->0),同时其上下左右的格子(如果存在)也会跟着翻转。
PIPI想知道最少操作多少次才能使得矩阵中的值全部为0?
请你输出操作次数最少的方案,如果答案不唯一,输出字典序最小的一组。如果没有合法的方案,输出“IMPOSSIBLE”。
PS:这里的字典序指的是将你输出的01矩阵逐行拼接在一起形成的01串的字典序。

Input

第一行两个正整数n,m.(n<=15,m<=15)
接下里n行给出一个n*m的01矩阵。

Output

如果有合法方案,输出n行,每行m个数,每个数代表该位置的翻转次数。
若无答案,输出IMPOSSIBLE”。

Sample Input

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

Sample Output

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