Fill the Crossword

A local newsletter has decided to start running a crossword puzzle in each issue. Instead of buying premade puzzles, the editors want to build puzzles in shapes of their own choosing using words they pick themselves. As the programmer, you have decided to solve this once and for all with your computer.

A crossword grid looks like this:

..#......
#.#......
#########
#.#.#...#
#.#.....#
######..#
#.#......

Each maximal run of two or more # marks in a row or a column represents a single word, one letter per mark. Where a horizontal word and a vertical word cross, the shared cell must hold the same letter in both.

Write a program that fills a given grid with a given set of words so that:

• every # cell in the grid holds exactly one letter;
• no other cell (.) holds a letter;
• every word in the list appears in the grid exactly once, with no word left unused; and
• no word (or other letter sequence) that is not in the list appears in the grid.

A word that merely sits inside a longer word (for example BRIGHT inside BRIGHTLY) does not count as an appearance of the shorter word. You may assume that every word in the list is distinct within a puzzle, and that a given grid and word list admit at most one possible layout.

The first line contains an integer: the number of datasets. For each dataset, the first line contains two integers w h ($2 \le w, h \le 15$), where w is the puzzle width and h is its height. The next h lines give the crossword grid in the format shown above. Every word run in the puzzle has length at least 2. The next line contains an integer c ($1 \le c \le 100$), the number of words, and the following c lines list the words, one per line.

For each dataset, first print the heading Puzzle #x, where x is 1 for the first dataset, 2 for the second, and so on. Then, if the puzzle cannot be completed with the given grid and word list, print I cannot generate this puzzle.; otherwise print the solved grid. The solved grid has the same h lines of w characters each, where every # cell is replaced by its assigned letter and every . cell stays ..