描述

柏拉图认为，我们所感知到的只是现实的一个影子。最近的考古发掘揭示了一些证据，表明这种信念可能是由柏拉图年轻时对巧妙设计的方块的把玩所促成的。这些方块具有一种奇特的属性，当将任何一个面朝向光源时，它们会投射出各种字母、数字、形状和图案的影子。对于一个角上的三个面，它们有可能对应着三种不同的影子图案。当然，相对的面所投射出的影子是彼此的镜像。

这些方块是通过将小立方体粘合在一起形成一个单一的、相连的物体。例如，下面的图形逐层展示了一个方块的内部结构，这个方块能够投射出字母 “E”、“G” 或 “B” 的影子。

只发现了一部分方块，但是好奇的科学家们想要确定可能出现的影子组合。你的程序，也就是这个问题的解决方案，将会帮助他们！程序将输入几组影子图案，对于每一组，程序会报告是否能够构造出一个实体，使其投射出这些影子。

输入

输入包含一系列数据集，每个数据集指定一个维度和三个影子图案。每个数据集的第一行包含一个正整数 $1 \leq n \leq 20$，用于指定输入图案的维度。数据集的其余部分由 $3n$ 行组成，每行包含一个由 $n$ 个 “X” 和 “-” 字符组成的字符串。每 $n$ 行一组代表一个图案。在出现 “X” 的地方，最终的实体应该投射出影子，在出现 “-” 的地方，光线应该能够穿过。对于这个问题，假设输入的图案在每个边缘上至少有一个 “X”。输入在遇到一行只包含一个表示维度的零（代替有效维度）时结束。

输出

对于输入中的每个数据集，输出数据集编号和以下消息之一：

Valid set of patterns（有效的图案集）

Impossible combination（不可能的组合）

对于一组图案要被认为是有效的，必须能够通过将单位立方体沿着它们的面粘合在一起，构造出一个能够投射出每个输入图案影子的单件实体。

5
XXXXX
X----
X--XX
X---X
XXXXX
XXXXX
X----
XXXXX
X----
XXXXX
XXXXX
X---X
XXXX-
X---X
XXXXX
3
X--
-X-
--X
XX-
XXX
-XX
-XX
XXX
XX-
0

Data set 1: Valid set of patterns
Data set 2: Impossible combination

来源

大纽约地区 2001 年