[Usaco2007 Open]Fliptile 翻格子游戏

约翰知道，快乐而又聪明的奶牛能够产出更多牛奶，因此他为奶牛们设计了一个翻瓦片的益智游戏。

游戏在一个 $M\times N$ 的网格上进行，每个格子中都有一块可以翻转的瓦片。瓦片一面为黑色，另一面为白色。翻转一块瓦片时，它会由黑色变为白色，或由白色变为黑色。由于奶牛的蹄子十分巨大，每当它们翻转某块瓦片时，与该瓦片有公共边的所有相邻瓦片也会同时翻转。

请确定最少需要进行多少次翻转，才能使所有瓦片均为白色面朝上，并输出一种达到最少翻转次数的方案。如果存在多种最优方案，则将输出结果视为字符串，输出其中字典序最小的方案。如果无法使所有瓦片均为白色面朝上，则输出 IMPOSSIBLE。

输入格式

第一行包含两个以空格分隔的整数 $M$ 和 $N$，分别表示网格的行数和列数。

接下来 $M$ 行，每行包含 $N$ 个以空格分隔的整数，表示瓦片的初始状态。其中，$0$ 表示白色面朝上，$1$ 表示黑色面朝上。

输出格式

如果存在可行方案，输出 $M$ 行，每行包含 $N$ 个以空格分隔的整数，表示对应位置的翻转次数。

如果不存在可行方案，输出一行 IMPOSSIBLE。

样例输入

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

数据范围

• $1\le M\le 15$；
• $1\le N\le 15$；
• 每块瓦片的初始状态为 $0$ 或 $1$。

来源与许可

本题为 USACO 2007 Open 试题「Fliptile 翻格子游戏」，题面与测试数据整理自 BZOJ。

样例 1

输入

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