P13869 [SWERC 2020] Fantasmagorie

:::align{center}  :::

Émile 的梦境中，经常出现人或动物变形为其他形态的场景。Émile 希望将他梦境中迷人的世界展示给大家，于是打算制作第一部动画片，当然是黑白的。在醒来之后，Émile 只记得梦中出现的初始形态和最终形态，而变形的过程他已经忘记了，因此他希望你能够重现这些“变形”，详细描述从第一幅图像变换到第二幅图像的步骤。 Émile 梦中的图像不是随意的黑白图像，它们满足以下三个约束条件。首先，图像的边界上的所有像素——最左和最右的列，以及最上和最下的行——颜色相同。其次，图像中不包含任何形状如下的 $2 \times 2$ 正方形： :::align{center}  或 。 ::: 第三个约束更复杂，可以描述如下。将图像划分为区域，定义为图像中**连通的同色区域**，即它们形成像素的最细划分，使得任何两个相邻且同色的像素属于同一区域。如果两个区域包含相邻的像素，则认为它们相邻。在 Émile 的图像中，每个区域最多与两个其他区域相邻，而包含边界像素的区域最多只与一个其他区域相邻。 你将得到两幅大小相同的 $W \times H$ 的黑白图像，你的目标是找到一个从第一幅图像到第二幅图像的“变形”。从图像 $A$ 到图像 $B$ 的变形是一系列图像，其要求如下： - 序列以 $A$ 开始，以 $B$ 结束； - 每幅图像（除了第一幅）可以通过翻转一个像素而从前一幅图像得到； - 每幅图像都必须满足上述三个约束； - 在变形过程中，每种颜色的区域数量不得变化。

输入的第一行包含两个空格分隔的整数：$W$ 和 $H$。 随后是 $H$ 行，按行从上到下描述第一幅图像。每行由 $W$ 个字符组成，描述该行的 $W$ 个像素，从左到右： - 若第 $k$ 个像素为白色，则字符为 `.`； - 若第 $k$ 个像素为黑色，则字符为 `#`。 最后是 $H$ 行，按相同格式描述第二幅图像。

如果不存在可行的变形，输出一行单独的单词 `IMPOSSIBLE`。否则，输出一种可能的变形方式： 如果第 $k+1$ 幅图像是通过翻转第 $k$ 幅图像中列 $c$、行 $r$ 的像素得到的（$0 \le c < W$ 且 $0 \le r < H$，其中 $c = 0$ 表示最左列，$r = 0$ 表示最上行），则第 $k$ 行输出 $(c, r)$。

所有测试点满足以下限制： - $1 \le H \le 64$； - $1 \le W \le 103$； - Émile 的第一幅图像和最后一幅图像是不同的； - 输出的像素翻转次数不超过 $250\,000$ 次。