题目描述

在一个幻想世界里，有块矩形岛屿。这座岛屿被划分成了 $R$ 行 $C$ 列的方格。

有些方格无人居住，而有些方格被以下某一种生物占据：精灵，人类，矮人或者霍比特人。占据同一格子的生物在这一格子组成了一个村庄。

为了防止恶魔的袭击，他们需要结成联盟。定义每个村庄相邻四个方向（上下左右）的村庄为这个村庄的邻居。

每种生物分别要满足以下条件：

• 精灵：只需要与一个邻居结盟；
• 人类：需要与两个邻居结盟，且这两个邻居不能在上下或者左右方向；
• 矮人：需要与三个邻居结盟；
• 霍比特：需要与四个邻居结盟（即所有邻居）。

你的任务是确定岛上的所有村庄是否都能与相应数量的邻居结盟（即可能会出现一些邻居并没有结盟）。如果能，则输出联盟的结构。否则输出 Impossible!。

注意：结盟的关系是双向的。

输入格式

输入第一行两个整数 $r,c$。

接下来的 $r$ 行，每行 $c$ 个 $0\sim 4$ 之间的数字，描述岛屿的人口分布状态。

• 0：此地无村庄；
• 1：此地为精灵村庄；
• 2：此地为人类村庄；
• 3：此地为矮人村庄；
• 4：此地为霍比特村庄。

可以注意的技巧：输入的数字对应该地所需的联盟数量。

输出格式

如果无法全部结盟则输出 Impossible!。

否则，输出以下格式的地图：

每块地都作为一个 $3\times 3$ 的矩阵输出。如果该地无人居住，则输出全部输出为 .。如果该地有村庄，则在中心输出一个 O。如果这个村庄与一些村庄结盟，那么在 O 上下左右四个方格输出 X 来表示结盟。

对于每种生物，所有可能的输出格式如下：

(elves 表示精灵，humans 表示人类，dwarves 表示矮人，hobbits 表示霍比特人）

如果有多种方案，输出其中任意一种，本题使用 SPJ。

3 4
2 3 2 0
3 4 3 0
2 3 3 1

............
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXOXXO.
............

1 2
2 1

Impossible!

提示

数据规模与约定

• 对于 $55\%$ 的数据，保证 $\min(r,c)\le 10$；
• 对于另 $15\%$ 的数据，保证 $r\times c\le 20$；
• 对于另 $10\%$ 的数据，保证地图中只有无人区和人类；
• 对于 $100\%$ 的数据，保证 $1\le r,c\le 70$。

说明

题目译自 CEOI 2010 day 1 T1 alliances。

翻译版权为题目提供者