체임버스 세라믹 난제

문제

체임버스 건설(CCC)은 가장 큰 고객에게 정해진 기한 안에 타일 바닥을 시공하기로 계약했다. 그런데 타일을 주문한 직원이 주문 직후 복권에 당첨되어 떠나 버리는 바람에, 각 타일을 어디에 놓아야 하는지에 대한 기록이 전혀 남지 않았다. 게다가 주문된 타일이 모두 단순한 정사각형인 것도 아니다. 각 타일은 4개의 단위 정사각형으로 이루어져 있으며, 아래 7가지 모양 중 하나를 가진다.

XXXX    XX      XX       XX     X       XXX      X
        XX       XX     XX      XXX     X       XXX

일정이 매우 촉박해 타일을 다시 주문할 수는 없다. 9개의 타일이 도착하면, 이들을 어떻게 배치할지(또는 어떻게 놓아도 방을 채울 수 없는지) 판단해야 한다. 상자 속 타일에는 A부터 I까지 순서대로 이름이 붙어 있다. 시공할 방은 한 변이 6칸인 6×6 격자이므로, 9개의 타일이 방을 빈틈없이 정확히 덮어야 한다.

배치 알고리즘

CCC의 관리자는 시공자가 반드시 따라야 하는 절차를 다음과 같이 정했다.

시공자는 항상 빈 칸이 남아 있는 가장 위쪽 행에서, 그 행의 가장 왼쪽 빈 칸을 채운다.
그 목표 칸을 채우기 위해, 상자에서 그 칸을 덮을 수 있는 가장 앞선 타일(A에 가장 가까운 타일)을 사용한다. 타일은 먼저 위 그림에 그려진 방향 그대로 놓아 보고, 맞지 않으면 시계 방향으로 90° 돌려 다시 시도한다(최대 3번까지 회전). 타일은 회전할 수 있지만 뒤집을 수는 없다.
놓인 타일은 6×6 방 밖으로 나가서는 안 되며, 다른 타일과 겹쳐서도 안 된다.

예를 들어 타일 A와 B가 다음과 같이 놓여 있다면,

AABBBZ
 AA B

다음에 놓을 타일은 Z로 표시된 칸(빈 칸이 남아 있는 가장 위쪽 행의 가장 왼쪽 빈 칸)을 채우도록 놓아야 한다.

시공자는 방을 다 채우거나 현재 배치로는 더 이상 완성할 수 없을 때까지 이 규칙에 따라 타일을 계속 놓는다. 막다른 상황에 이르면 한 타일씩 되돌아가는데, 먼저 가장 최근에 놓은 타일의 남은 회전들을 시도하고, 그다음 순서의 타일을 시도한다. 이 되돌아가기를 반복하여 완전한 배치를 찾거나 모든 조합을 다 시도할 때까지 계속한다. 이 절차로 방 전체를 덮을 수 있으면 바닥을 may be tiled로, 그렇지 않으면 may not be tiled로 판단한다.

입력

첫 번째 줄에는 데이터 집합의 개수 $N$이 주어진다.

다음 $N$개의 줄에는 각각 9개의 정수가 주어지며, 하나의 데이터 집합을 나타낸다. 첫 번째 정수는 타일 A의 모양, 두 번째 정수는 타일 B의 모양이며, 이런 식으로 타일 I까지 이어진다. 각 정수는 1 이상 7 이하이며, 위 그림의 모양 중 하나를 가리킨다. 모양은 가장 왼쪽이 1, 가장 오른쪽이 7이다.

출력

각 데이터 집합마다 먼저 Data Set k 형식의 줄을 출력한다. 여기서 $k$는 1부터 시작하는 데이터 집합의 순번이다.

다음 줄에는 The floor may be tiled. 또는 The floor may not be tiled. 중 하나를 출력한다.

바닥을 채울 수 있다면, 이어지는 6개의 줄에 최종 6×6 배치를 출력한다. 각 칸에는 그 칸을 덮은 타일의 이름(A–I, 입력 줄에서의 위치와 일치)을 적으며, 각 줄은 정확히 6개의 문자로 이루어진다.

각 데이터 집합 뒤에는 빈 줄을 하나 출력한다. 마지막 데이터 집합 뒤에는 End of Output이라고 적힌 줄을 출력한다.