Description

你的游戏公司刚刚订购了许多有 $64$ 个空白单元格的正方形游戏棋盘，原本打算将它们制作为国际象棋棋盘，但你的老板突然宣布国际象棋已经过时。为了充分利用这些棋盘，你设计了一种新的拼图游戏，使用“瓷砖”。

一个“瓷砖”是由若干个单元格通过边相连组成的连续区域，且可以放入一个 $3\times 3$ 的单元格正方形内。例如，以下是一些合法的瓷砖示例（每个 @ 表示瓷砖的一部分，额外的 . 字符用于填充）：

... @@@ @@@ .@@
... @@@ @.@ @.@
.@. @@@ @.. @@@

以下则不是合法的瓷砖：

@@. @.@ .@@.
... .@. @@@@
.@@ @.@ .@@.

当玩家在棋盘上放置瓷砖时，瓷砖的单元格必须完全覆盖棋盘上未被其他瓷砖覆盖的某些单元格。即使经过任意平移、90 度倍数的旋转和/或翻转后，仍然视为同一种瓷砖，玩家在放置时可以进行这些操作。例如，以下所有都是同一种瓷砖（还可能有其它变体）：

.@. ..@ @.. ... @@.
@@. .@@ @@. .@@ .@@
@.. .@. .@. @@. ...

为了制作拼图，你会将棋盘上的一个或多个单元格涂成红色。玩家需要通过放置瓷砖，使所有红色单元格都被覆盖，且没有其他单元格被覆盖。为节省制造成本，玩家只会获得一种瓷砖，但会获得恰好足够多的该瓷砖以覆盖所有红色单元格。

你的任务是决定哪些棋盘单元格需要涂成红色。不幸的是，你的老板还在犹豫究竟用哪两种瓷砖。你厌倦了等待，于是决定尝试涂色，使得无论最终选择哪种瓷砖，拼图都能被解出。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试用例；每组包含四行。前三行每行有三个字符，然后一个空格，再三个字符。第四行为空行。

每组测试用例中，空格将左侧和右侧的两个 $3\times 3$ 网格分开。每个网格表示一种瓷砖的形状。网格中的每个字符要么是 @（表示瓷砖的一部分），要么是 .（表示不是瓷砖的一部分，仅用于填充以便形状清晰）。注意，这些 . 与拼图或棋盘无关，仅用于展示瓷砖形状。保证输入的两种瓷砖不是同一种瓷砖（如上文所述）。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 为 POSSIBLE（存在解）或 IMPOSSIBLE（不存在解）。如果存在解，则再输出八行，每行十七个字符，形成两个 $8\times 8$ 的网格，中间用一个空格分隔。每个网格用点（.）表示空白单元格，或用如下 64 个字符之一：

!?0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

表示每个瓷砖的不同部分。在每个 $8\times 8$ 网格中，相同的非点字符表示同一个瓷砖的不同部分，不同字符表示不同的瓷砖。左侧网格中的每个瓷砖必须与输入左侧的瓷砖一致（允许旋转、平移和翻转），右侧网格同理。两个 $8\times 8$ 网格中非点字符所在的单元格集合必须完全相同，且非空。

如果有多组合法解，可以输出任意一组。

4
.@@ .@.
.@. .@.
.@@ @@.

@@@ @@@
@.@ @@@
@@@ @@@

.@. ...
@@. .@@
@.. ...

... ..@
... ..@
@.. ...

Case #1: POSSIBLE
....11.. ....11..
...221.. ...221..
...211.. ...321..
...22... ...32...
.333.... .433....
4343.... 5444....
444..... 555.....
........ ........
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
........ ........
..T..I.. ..T..I..
.TT..II. .tT..Ii.
.T....I. .t....i.
........ ........
.LL..EE. .LL..EE.
..LLEE.. ..llee..
........ ........
Case #4: POSSIBLE
the.CODE AAB.CDDE
Jam.2018 FFB.CGGE
........ ........
World... HHIIJ...
.FiNALS. .KLLJMM.
.cup.... .KNN....
........ ........
TRIUMPH! OOPPQQRR

Hint

样例解释

样例输出展示了样例的某一组答案，其他答案也可能合法。

在样例第 2 组中，不存在一组红色单元格能使得无论选择哪种瓷砖都能解出拼图。

在样例第 3、4 组中，所选的红色单元格不要求连通。注意，输入中瓷砖的点（.）不参与拼图，仅用于展示。例如，以下输入也可以接受：

... ...
.@. .@.
... .@.

此外，该输入与样例第 4 组同构，因此不会同时出现在同一测试集中。

第 1 组数据范围（可见，且为唯一测试集）

• $T = 595$。（包含所有可能的测试用例，按同构分类）
• 输入中每个瓷砖的单元格通过边相连，形成一个连通块。
• 输入的两种瓷砖不是同一种瓷砖（如上文所述）。

由 ChatGPT 4.1 翻译