Domino Tiling

Time limit1sMemory limit128 MB

Summary

Cover a grid with pre-placed tiles and all given dominoes, then output the lexicographically smallest valid tiling and the count of other tilings.

Level: Hard8 of 10
Topics: Backtracking, Dynamic programming, Bit manipulation, Implementation
Solved: No attempts yet

Problem

The aliens want to conquer the entire universe, so it is no surprise that their favorite game is played with dominoes. A domino is a $1 \times 2$ tile with a digit from $0$ to $9$ written on each of its two halves. The game board is a rectangular grid, and every unit square also holds a digit from $0$ to $9$ .

Your task is to cover the whole board with a given set of dominoes. A domino may be placed on two adjacent squares only if the two digits on the domino equal the two digits written on those squares. A domino may be placed as is or rotated by $90°$ , $180°$ , or $270°$ , so a domino with halves $a$ and $b$ fits any pair of adjacent squares whose digits are $a$ and $b$ in either arrangement. No two dominoes may overlap, and each supplied domino may be used at most once.

Some squares already hold pre-placed tiles; these must remain exactly where they are. You must place all of the supplied dominoes so that, together with the pre-placed tiles, they cover every square of the board.

Input

The input contains several game descriptions.

The first line of each description contains three space-separated integers: the board height $M$ , the board width $N$ , and the number of available dominoes $K$ , where $1 \le M \le 20$ , $1 \le N \le 20$ , at least one of $M$ and $N$ is even, $2 \le M \cdot N \le 110$ , and $1 \le K \le \lfloor M \cdot N / 2 \rfloor$ .

The second line contains $K$ pairs of integers (that is, $2K$ integers) giving the two digits on each available domino. No two dominoes are identical, even when one of them is rotated by $180°$ ; in other words the unordered digit pairs are pairwise distinct. None of the pre-placed tiles appears among these $K$ dominoes.

Each of the next $M$ lines contains $N$ space-separated entries. The entry in row $i$ and column $j$ ( $0 \le i < M$ , $0 \le j < N$ ) is either the capital letter X, meaning that square already holds a pre-placed tile, or a digit $A_{i,j}$ with $0 \le A_{i,j} \le 9$ .

Descriptions are separated by blank lines. The input ends with a line containing three zeros (0 0 0), which must not be processed.

Output

For each game, decide whether all dominoes can be placed so that, together with the pre-placed tiles, they cover the whole board.

If it is possible, output the board as an $M \times N$ grid of characters, one row per line with no spaces, using:

[ and ] for the left and right halves of a horizontally placed domino,
n and u for the upper and lower halves of a vertically placed domino,
X for a square covered by a pre-placed tile.

Several valid tilings may exist. To make the answer unique, output the lexicographically smallest grid: read the grid row by row from top to bottom and, within each row, from left to right, forming one string, and compare characters by their ASCII value (so the order is X < [ < ] < n < u); output the tiling whose resulting string is smallest.

After the $M$ grid rows, print a single line with the number of other valid tilings, that is, the total number of valid tilings minus one.

If no valid tiling exists, print a single line containing the word impossible instead.

Print one blank line between consecutive game results.

Examples3

Example 1

Input

4 5 9
0 0 0 1 1 1 3 3 0 2 1 2 0 3 2 2 2 3
1 2 2 0 X
2 1 0 0 X
2 1 3 3 3
2 3 0 1 0

2 3 3
1 1 2 2 3 3
1 2 3
1 3 2

2 3 3
1 1 2 2 3 3
1 2 3
1 2 3

0 0 0

Expected output

[][]X
nn[]X
uu[]n
[][]u
3

impossible

nnn
uuu
0

Example 2
Input
```
2 1 1
5 5
5
5
0 0 0
```
Expected output
```
n
u
0
```
Example 3
Input
```
2 2 2
1 2 2 3
1 2
2 3
0 0 0
```
Expected output
```
[]
[]
1
```