스도미노쿠

스도쿠가 세계적으로 유행한 뒤로 비슷한 퍼즐이 많이 등장했다. 그중 하나가 스도쿠와 도미노를 결합한 스도미노쿠이다.

이 퍼즐은 스도쿠 규칙을 따른다. $9 \times 9$ 크기의 격자를 $1$부터 $9$까지의 숫자로 채우되, 다음 조건을 모두 만족해야 한다.

• 각 행에는 $1$부터 $9$까지의 숫자가 정확히 한 번씩 나타난다.
• 각 열에는 $1$부터 $9$까지의 숫자가 정확히 한 번씩 나타난다.
• 격자를 나눈 아홉 개의 $3 \times 3$ 정사각형 각각에도 $1$부터 $9$까지의 숫자가 정확히 한 번씩 나타난다.

스도미노쿠의 격자에는 이미 $1$부터 $9$까지의 숫자가 한 칸씩(모두 아홉 칸) 적혀 있고, 나머지 $72$칸은 도미노 타일 $36$개로 덮어야 한다. 각 도미노 타일에는 서로 다른 두 숫자가 적혀 있으며, $1$부터 $9$까지의 숫자로 만들 수 있는 서로 다른 쌍이 모두 하나씩 존재한다(예: $1+2, 1+3, \dots, 1+9, 2+3, \dots$). $1+2$와 $2+1$은 같은 타일이므로 구분하지 않는다. 도미노는 가로 또는 세로로 놓을 수 있고, $3 \times 3$ 정사각형의 경계를 걸쳐 놓아도 된다.

칸의 위치는 다음과 같이 나타낸다. 행은 위에서 아래로 $A$부터 $I$까지의 알파벳으로, 열은 왼쪽에서 오른쪽으로 $1$부터 $9$까지의 숫자로 표시하며, 한 칸의 위치는 (행 문자)(열 숫자)로 쓴다. 예를 들어 $B3$은 $B$행 $3$열을 뜻한다.

스도미노쿠 퍼즐의 초기 상태가 주어졌을 때, 퍼즐을 완성하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 이미 놓여 있는 도미노의 개수 $N$이 주어진다 ($10 \le N \le 35$).

다음 $N$개의 줄에는 도미노 하나의 정보가 U LU V LV 형식으로 주어진다. $U$는 도미노에 적힌 한 숫자이고 $LU$는 그 숫자가 놓인 칸의 위치(길이 $2$의 문자열)이며, $V$는 도미노에 적힌 다른 숫자이고 $LV$는 그 위치이다. 한 도미노를 이루는 두 칸은 항상 가로 또는 세로로 인접해 있다.

그 다음 줄에는 이미 적혀 있는 아홉 개의 숫자의 위치가 $1$부터 $9$까지 차례대로 주어진다. 위치는 도미노와 같은 방식으로 나타낸다.

도미노와 숫자가 놓인 칸은 서로 겹치지 않는다.

입력의 마지막 줄에는 $0$이 하나 주어지며, 이는 입력의 끝을 의미한다.

각 퍼즐에 대해 먼저 Puzzle k를 출력한다. 여기서 $k$는 입력에서의 순서(1부터 시작)이다. 이어서 완성된 $9 \times 9$ 격자를 한 줄에 아홉 자리씩, 모두 아홉 줄로 출력한다.

정답이 유일한 경우만 입력으로 주어진다.