크리스털 감옥

크리스털 감옥은 색이 다른 크리스털 정육면체를 쌓아 만든 직육면체 장식품이다. 정육면체마다 중심에 빛나는 심이 박혀 있어서 이런 이름이 붙었다. 여러 색의 반사광이 겹치면서 무늬가 나타난다.

제조사는 이 제품을 많이 팔고 싶었고, 보기 좋은 색 배치가 가장 중요하다고 판단했다. 괜찮은 무늬를 여럿 내놓으면 한 사람이 여러 개를 살 것이라고 봤다. 그런데 무늬를 설계할 사람이 없어서 임시 디자이너를 고용했다.

대량 생산에는 제약이 하나 있다. 같은 색 정육면체는 모두 서로 붙어 있어야 한다. 그래서 공장에 넘기는 설계도는 같은 색 정육면체가 이루는 덩어리, 즉 블록의 모음이어야 한다. 회사는 디자이너에게 이 형식으로 설계를 넘기라고 요청했다.

일주일 뒤 디자이너가 여러 무늬를 보내왔다. 처음에는 괜찮아 보였지만, 그중 몇 개는 직육면체를 만들 수 없는 무늬였다. 그림 솜씨는 좋았지만 입체 감각이 부족했다.

다시 그려 달라고 할 시간이 없다. 못 쓰는 무늬는 버려도 되지만 어느 것이 못 쓰는 무늬인지 손으로 가려내는 데도 시간이 오래 걸린다. 그래서 프로젝트 책임자가 당신에게 도움을 요청했다.

주어진 블록으로 직육면체를 만들 수 있는지 판정하는 프로그램을 작성하라. 블록은 회전해서 놓을 수 있다. 뒤집어서 거울상으로 쓰는 것은 안 된다.

입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합의 형식은 다음과 같다.

W D H N
Block1
Block2
...
BlockN

첫 줄에 양의 정수 네 개 $W$, $D$, $H$, $N$이 주어진다. $W$, $D$, $H$는 만들려는 크리스털 감옥의 가로, 세로, 높이이고, $N$은 색의 개수이자 블록의 개수다.

이어지는 줄은 색이 다른 블록 $N$개를 설명한다. 블록 하나의 형식은 다음과 같다.

w d h
c111 c211 ... cw11
c121 c221 ... cw21
...
c1d1 c2d1 ... cwd1
c112 c212 ... cw12
c122 c222 ... cw22
...
c1d2 c2d2 ... cwd2
...
c11h c21h ... cw1h
c12h c22h ... cw2h
...
c1dh c2dh ... cwdh

첫 줄에 양의 정수 세 개 $w$, $d$, $h$가 주어진다. 각각 블록의 가로, 세로, 높이다. 그 뒤로 $(d + 1) \times h$개의 줄이 블록 모양을 나타낸다. 아래층부터 위층까지 층마다 단면을 적으며, 한 층은 문자 $w$개로 된 줄 $d$개로 나타낸다. 각 문자 $c_{xyz}$는 * 또는 .이고, 한 줄의 문자는 사이에 공백 없이 이어 붙여 적는다. *는 그 자리에 크리스털 정육면체가 있다는 뜻이고, .은 없다는 뜻이다. 한 층의 $d \times w$ 문자표 뒤에는 빈 줄이 하나씩 온다.

입력의 끝은 0이 네 개 적힌 줄로 표시한다.

다음을 가정해도 된다.

• $1 \le W, D, H, w, d, h \le 3$
• $1 \le N \le 27$
• 각 블록에는 크리스털 정육면체가 하나 이상 있고, 한 블록의 정육면체는 모두 이어져 있다.
• 크리스털 정육면체의 총 개수는 $W \times D \times H$와 같다.

데이터 집합마다 주어진 블록으로 $W \times D \times H$ 직육면체를 만들 수 있으면 Yes를, 만들 수 없으면 No를 한 줄에 출력한다.