009 - 立方体表面パズル

時間制限 8 秒 / メモリ制限 256 MB / 得点 40 / x 0 /


TLE
8sec
MLE
256MB
得点
40

問題

立方体表面パズルとは,6 つのピースを適切に組み合わせて表面に欠けのない中空の立方体を作るパズルである. パズルの各ピースは,単位小立方体を平面上に格子状に並べてできている. 1 辺の長さ n の立方体を作るピースは以下の 2 領域からなる.

  • 中央領域 (青): 1 辺の長さ n−2 の正方形領域.単位立方体で埋め尽くされている.
  • 周辺領域 (赤): 中央部分の外縁の幅 1 の領域. この領域の単位正方形の上には何もないか,単位立方体があるかである.
各ピースの単位立方体は面でつながっている. 各ピースは自由に回転して使ってよく, 表裏のどちらが組み立てた立方体の内側・外側になってもよい. 各ピースの中央領域上の単位立方体は組み立てた立方体の各面の中央に来なくてはならない.

たとえば,図 E-1 の 6 つのピース (Sample Input の最初のデータセットである) が与えられたとする. このとき,図 E-2 のように組み立てることで立方体を作れる.

図 E-1 Sample Input の最初のデータセットのピース
図 E-2 立方体の組み立て

Hadrian Hex 氏はたくさんの立方体表面パズルを収集していた.あるとき,それらのピースが混ざってしまい,どのピースを組み合わせれば立方体を作れるか分からなくなってしまった. そこで,与えられたピースの組合せによって立方体ができるかを判定するプログラムを作って Hex 氏を助けて欲しい.

Input

入力は最大 200 データセットからなり,各データセットは次の形式で表される.

n
x1,1x1,2x1,n
x2,1x2,2x2,n

x6n,1x6n,2x6n,n

各データセットの 1 行目には作る立方体の 1 辺の長さ n (3 ≤ n ≤ 9, n は奇数) が与えられる. 続く 6n 行に,6 つのピースが与えられる. 各ピースは n 行で表される. 各行は格子の 1 行に対応し,その行の各文字 (‘X’ または ‘.’) は対応する単位正方形上の単位立方体の有無を意味する. ‘X’ なら単位立方体があり,‘.’ なら空である.

各ピースの中央領域は各ピースのデータの中央に位置する.

入力の終わりは,ゼロだけからなる行で表される.

Output

各データセットについて,立方体ができる場合には “Yes”,できない場合には “No” を出力せよ.

Sample Input

5
..XX.
.XXX.
XXXXX
XXXXX
X....
....X
XXXXX
.XXX.
.XXX.
.....
..XXX
XXXX.
.XXXX
.XXXX
...X.
...X.
.XXXX
XXXX.
XXXX.
.X.X.
XXX.X
.XXXX
XXXXX
.XXXX
.XXXX
XX...
.XXXX
XXXXX
XXXXX
XX...
5
..XX.
.XXX.
XXXXX
XXXX.
X....
....X
XXXXX
.XXX.
.XXX.
.....
.XXXX
XXXX.
.XXXX
.XXXX
...X.
...X.
.XXXX
XXXX.
XXXX.
.X.X.
XXX.X
.XXXX
XXXXX
.XXXX
.XXXX
XX...
XXXXX
XXXXX
.XXXX
XX...
0

Output for the Sample Input

Yes
No