초콜릿 트러플 퍼즐

사촌이 최근 3 x 3 격자에 트러플을 배치하는 게임을 샀다. 그보다 한 수 앞서기 위해, 퍼즐을 자동으로 푸는 프로그램을 작성하기로 했다. 그러면 그가 당신과의 대결에서 퍼즐을 풀 가능성은 없다.

게임에는 아홉 개의 트러플이 있고, 모든 퍼즐에서 이 아홉 개를 모두 사용한다. 각 트러플은 맛이 바닐라(V), 딸기(S), 초콜릿(C) 중 하나이고, 모양은 정사각형(S), 원형(R), 삼각형(T) 중 하나이다. 속성 조합마다 트러플이 정확히 하나씩 있으며, 아홉 개를 모두 사용해야 한다. 각 퍼즐에서 아홉 개의 트러플을 3 x 3 보드에 하나씩 놓아야 한다. 편의상 칸은 첫 번째 행을 왼쪽에서 오른쪽으로 1, 2, 3, 두 번째 행을 4, 5, 6, 세 번째 행을 7, 8, 9로 번호 매긴다. 아래 그림과 같다.

각 퍼즐에는 단서 목록이 주어진다. 각 단서는 보드의 일부 영역에 대한 정보를 준다. 예를 들어 아래 단서는 오른쪽 위 모서리에 정사각형 딸기 트러플이 놓인 3 x 2 창이 있다는 뜻이다.

__ SS
__ __
__ __

3 x 3 보드에는 이런 3 x 2 창이 두 개뿐이다. 따라서 이 단서는 정사각형 딸기 트러플이 2번 칸이나 3번 칸에 있어야 한다는 것을 알려 준다. 단서는 회전할 수 없다.

다른 단서는 다음과 같다.

__ _S
__ RC
__ T_

이 단서도 3 x 2 창을 나타낸다. 창의 오른쪽 열에서 위쪽 행에는 딸기 트러플(모양은 무관)이, 가운데 행에는 둥근 초콜릿 트러플이, 아래쪽 행에는 삼각형 트러플(맛은 무관)이 있어야 한다. 창의 크기 때문에 이 조건은 보드의 가운데 열이나 오른쪽 열 중 하나에서 성립해야 한다.

초콜릿 퍼즐의 해가 하나로 정해지는 단서 집합이 주어지면, 그 해를 구하라.

첫 줄에는 풀어야 할 퍼즐의 수를 나타내는 양의 정수 n이 주어진다. 그 뒤에 퍼즐들이 이어진다. 각 퍼즐의 첫 줄에는 그 퍼즐의 단서 개수를 나타내는 양의 정수 c (1 ≤ c ≤ 10)가 주어진다. 그 뒤에 단서들이 이어진다. 각 단서의 첫 줄에는 단서 창의 행 수와 열 수를 나타내는 공백으로 구분된 두 정수 x (1 ≤ x ≤ 3)와 y (1 ≤ y ≤ 3)가 주어진다. 다음 x 줄이 단서이며, 각 줄에는 정확히 한 칸의 공백으로 구분된 y개의 코드가 있다. 각 코드는 두 글자이다. 첫 글자는 {'','S','R','T'} 중 하나로 모양을, 둘째 글자는 {'','V','S','C'} 중 하나로 맛을 나타낸다. 밑줄은 그 속성이 고정되지 않았음을 뜻한다.

각 퍼즐의 출력 첫 줄은 "Puzzle #p:" 형식이며, p는 1부터 시작하는 퍼즐 번호이다. 다음 세 줄에 단서와 같은 코드를 사용해 퍼즐의 해를 출력한다. 각 퍼즐의 해는 하나뿐이므로, 올바른 해에는 밑줄이 나타나지 않는다. 각 테스트 케이스의 출력 뒤에는 빈 줄을 하나 남긴다. 샘플 출력에 나타난 형식을 따른다.