Boggle

Boggle is a game played with 16 dice that carry one letter on each face. The dice fill a 4x4 grid, and players look for words by joining letters on adjacent dice. In this problem you write a program that finds dictionary words in a letter grid the same way.

Inside a word, every letter must be adjacent to the previous letter in the grid, horizontally, vertically, or diagonally. One grid cell may be used at most once in a single word. The same letter may appear several times in a word when it comes from different cells.

In ordinary Boggle each face carries a single letter, with one exception. No face carries q by itself, and the two letters qu appear together instead. The grids here follow the same rule, so a cell holding q counts as the two letters qu.

The first line contains the number of dictionary words $W$ ($1 \le W \le 200$).

Each of the next $W$ lines contains one word made of 1 to 25 lowercase ASCII letters (a-z). All dictionary words are different.

The dictionary is followed by one or more letter grids. Each grid starts with a line holding its size $D$ ($2 \le D \le 8$), and the grid is a $D \times D$ square. The next $D$ lines each contain $D$ lowercase ASCII letters and give one row of the grid. A line holding 0 in place of $D$ ends the input.

For each grid, print the following.

1. Every dictionary word found in that grid, one per line, in alphabetical order.
2. A line holding a single hyphen -.