초입방체

4차원 초입방체는 테서랙트라고도 부른다. 단위 테서랙트는 좌표가 $(\pm 1/2, \pm 1/2, \pm 1/2, \pm 1/2)$인 16개 점의 볼록 껍질이고, 이 16개 점이 꼭짓점이다. 테서랙트에는 모서리가 32개, 정사각형 면이 24개, 정육면체 모양의 3차원 면이 8개 있으며 3차원 면을 셀이라고 부른다. 이 문제에서는 속이 빈 테서랙트만 다루므로, 테서랙트는 속이 찬 테서랙트의 경계를 뜻한다. 즉 테서랙트는 정사각형 면 24개, 모서리 32개, 꼭짓점 16개에서 서로 맞물리는 정육면체 셀 8개의 연결된 합집합이다.

테서랙트의 정사각형 면 24개 가운데 17개를 자르되 남겨 둔 면 7개로는 여전히 연결되어 있게 한다. 그다음 남겨 둔 면을 축으로 셀을 돌려 모든 셀이 같은 3차원 초평면에 놓일 때까지 펼친다. 이렇게 얻은 도형을 테서랙트의 3차원 전개도라고 한다. 정육면체를 모서리 12개 중 7개를 따라 자른 뒤 평면에 펼쳐 정사각형 6개짜리 전개도를 얻는 과정을 한 차원 올린 것이다.

3차원 공간에 놓인 트리 모양 8-폴리큐브가 주어진다. 8-폴리큐브는 옥토큐브라고도 부른다. 옥토큐브는 단위 정육면체 셀 8개를 면끼리 붙여 만든 도형이다. 더 정확히 말하면 두 셀의 교집합은 공집합, 점, 단위 선분, 단위 정사각형 중 하나다. 두 셀의 교집합이 정사각형이면 두 셀은 인접한다. 점이나 선분에서 만나는 셀은 인접하지 않는다. 옥토큐브의 인접 그래프는 셀 하나마다 정점 하나씩 8개를 두고 인접한 셀 쌍마다 간선을 놓은 그래프다. 인접 그래프가 트리이면 그 옥토큐브를 트리 모양이라고 한다.

주어진 트리 모양 옥토큐브가 테서랙트의 3차원 전개도인지 판정하라. 다시 말해 셀이 공유하는 정사각형을 따라 4차원 공간에서 접어 테서랙트를 만들 수 있는지 판정하라.

예를 들어 아래 그림의 가장 왼쪽을 보자. 트리 모양 옥토큐브의 뼈대가 그려져 있다. 셀 GHLKG1H1L1K1을 평면 GHLK를 축으로, 셀 FGKJF2G2K2J2를 평면 FGKJ를 축으로 원래 초평면 바깥의 4차원 방향으로 90도 돌린다. 그러면 점 G1이 G2와, 점 K1이 K2와 만나고 면 GKK2G2가 면 GKK1G1에 붙는다. 그 결과가 오른쪽에 있다. 4차원 방향은 원근으로 그린 3차원 위에 정사영으로 나타냈고, 원래 초평면을 벗어난 점은 속이 빈 점으로 표시했다.

셀 EFJIE1F1J1I1을 EFJI를 축으로, 셀 EHLIE2H2L2I2를 EHLI를 축으로 돌린다. 그 결과가 다음 그림의 왼쪽이다. 남은 과정은 이렇다. MNOPQRST를 MNOP를 축으로 돌리고, 이어서 MNOPQRST와 IJKLMNOP를 함께 IJKL을 축으로 돌린 뒤, ABCDEFGH를 EFGH를 축으로 돌린다. 마지막으로 맞닿는 면을 모두 붙이면 오른쪽 그림의 테서랙트가 된다.

첫째 줄에 주어진 옥토큐브를 담은 상자의 가로, 세로, 높이를 나타내는 정수 $m$, $n$, $k$가 주어진다 ($1 \le m, n, k \le 8$). 이어서 상자를 위에서 아래로 자른 직사각형 단면 $k$개가 주어진다. 각 단면은 $m$개 문자로 이루어진 $n$개 줄로 나타낸다. 각 문자는 빈 공간을 뜻하는 '.'이거나 단위 정육면체를 뜻하는 'x'다. 상자는 옥토큐브를 담기만 하면 되고 딱 맞을 필요는 없다. 입력은 항상 트리 모양 옥토큐브를 나타내므로 'x'는 정확히 8개다.

주어진 옥토큐브를 접어 테서랙트를 만들 수 있으면 "Yes"를, 그렇지 않으면 "No"를 한 단어로 출력한다.