考虑一个 4-超立方体,也称为超正方体(tesseract)。一个单位实心超正方体是一个 4D 图形,等同于 16 个笛卡尔坐标为 $(\pm\frac{1}{2}, \pm\frac{1}{2}, \pm\frac{1}{2}, \pm\frac{1}{2})$ 的点的凸包,这些点即为其顶点。它有 32 条边(1D)、24 个正方形面(2D)和 8 个立方体 3-面(3D),也称为胞(cells)。我们研究空心超正方体,并将超正方体定义为实心超正方体的边界。因此,超正方体是 8 个实心立方体(其胞)的连通并集,它们在 24 个超正方体的正方形面、32 条边和 16 个顶点处相互交汇。
让我们沿着超正方体的 24 个面中的 17 个进行切割,使其仍然通过保留的 7 个面保持连通。通过沿着保留的面旋转其构成的立方体,将超正方体展开到一个 3D 超平面中,直到其所有胞都位于同一个 3D 超平面内。其结果被称为超正方体的 3-网(3-net)。这个过程是 3D 立方体如何被切割并展开到 2D 平面上以产生由 6 个正方形组成的 2-网的自然推广。
在本题中,给定一个 3D 空间中的树状 8-多方块(8-polycube),也称为八方块(octocube)。八方块是由 8 个面面相连的单位立方体胞组成的集合。更正式地说,构成八方块的每一对立方体胞的交集要么为空,要么是一个点、一条单位线段(1D)或一个单位正方形(2D)。给定的八方块在以下意义上是树状的:考虑八方块的邻接图——一个具有 8 个顶点(对应于其 8 个胞)的图。如果一对胞相邻,则邻接图中存在一条边。当两个八方块胞的交集是一个正方形时,称它们相邻。在点或线处相交的胞不被视为相邻。当八方块的邻接图是一棵树时,称其为树状的。
你的任务是确定给定的树状八方块是否构成超正方体的 3-网。也就是说,这个八方块放置在 4D 空间的一个超平面上后,能否在 4D 空间中沿着其胞之间的交集正方形折叠成一个超正方体。
例如,看下面左侧的图片。它展示了树状八方块的线框图。将胞 $GHLKG_1H_1L_1K_1$ 绕平面 $GHLK$ 旋转,并将胞 $FGKJF_2G_2K_2J_2$ 绕平面 $FGKJ$ 在原始超平面之外的第 4 维度旋转 90 度。结果,点 $G_1$ 与 $G_2$ 重合,$K_1$ 与 $K_2$ 重合。面 $GKK_2G_2$ 与面 $GKK_1G_1$ 粘合。结果显示在右侧。第 4 维度被正交投影到透视显示的 3 个维度上。移出原始超平面的点用空心圆点标记。
旋转 $EFJIE_1F_1J_1I_1$ 绕 $EFJI$ 和 $EHLIE_2H_2L_2I_2$ 绕 $EHLI$。结果显示在左侧的下图中。其余步骤如下。将 $MNOPQRST$ 绕 $MNOP$ 旋转,然后将 $MNOPQRST$ 和 $IJKLMNOP$ 同时绕 $IJKL$ 旋转,并将 $ABCDEFGH$ 绕 $EFGH$ 旋转。最后一步是将所有相遇的面粘合在一起,得到右侧所示的超正方体。
输入格式
输入文件的第一行包含三个整数 $m, n, k$ —— 包含给定八方块的盒子的宽度、深度和高度($1 \le m, n, k \le 8$)。接下来的 $k$ 组行描述了从上到下盒子的矩形切片。每个切片由 $n$ 行描述,每行包含 $m$ 个字符。行上的字符要么是 ‘.’,表示空空间,要么是 ‘x’,表示一个单位立方体。保证输入文件描述的是一个树状八方块。
输出格式
如果给定的八方块可以折叠成超正方体,则向输出文件写入单词 “Yes”,否则写入 “No”。
样例
样例输入 1
3 3 4 ... .x. ... .x. xxx .x. ... .x. ... ... .x. ...
样例输出 1
Yes
样例输入 2
8 1 1 xxxxxxxx
样例输出 2
No