Su-domino-ku

After Sudoku became popular worldwide, many similar puzzles appeared. One of them, Su-domino-ku, combines Sudoku with dominoes.

This puzzle follows the rules of Sudoku. You must fill a $9 \times 9$ grid with the digits $1$ through $9$ so that all of the following hold:

• Each row contains each digit from $1$ to $9$ exactly once.
• Each column contains each digit from $1$ to $9$ exactly once.
• Each of the nine $3 \times 3$ squares that partition the grid also contains each digit from $1$ to $9$ exactly once.

In a Su-domino-ku grid, the digits $1$ through $9$ are already written, one per cell (nine cells in total), and the remaining $72$ cells must be covered by $36$ domino tiles. Each domino tile holds two different digits, and there is exactly one tile for every unordered pair of distinct digits from $1$ to $9$ (for example $1+2, 1+3, \dots, 1+9, 2+3, \dots$). Since $1+2$ and $2+1$ are the same tile, they are not distinguished. A domino may be placed horizontally or vertically, and it may straddle the border between two $3 \times 3$ squares.

Cell positions are written as follows. Rows are labeled $A$ to $I$ from top to bottom, columns are labeled $1$ to $9$ from left to right, and a cell position is written as (row letter)(column digit). For example, $B3$ denotes row $B$, column $3$.

Given the initial state of a Su-domino-ku puzzle, write a program that completes it.

The input consists of several test cases.

The first line of each test case contains the number $N$ of dominoes already placed ($10 \le N \le 35$).

Each of the next $N$ lines describes one domino in the format U LU V LV. $U$ is one digit written on the domino and $LU$ is the position of the cell holding it (a string of length $2$); $V$ is the other digit on the domino and $LV$ is its position. The two cells of a domino are always horizontally or vertically adjacent.

The following line gives the positions of the nine already-written digits, in order for $1$ through $9$. Positions use the same notation as the dominoes.

No cell is occupied by more than one domino or digit.

The last line of the input contains a single $0$, marking the end of the input.

For each puzzle, first print Puzzle k, where $k$ is its position in the input (starting from $1$). Then print the completed $9 \times 9$ grid as nine lines of nine digits each.

Only inputs with a unique solution are given.