Problem 1010: Treasure Island

(ACM S.E. U.S.A. Regional 2003, problem 10)

Description

Marketing of movies is a multi-million dollar industry. The Educational and Recreational Auxiliaries Unit (ERAU) creates word search puzzles with names of movie characters, actors, and other words to distribute to promote movies. Word search puzzles are grids of letters with words embedded horizontally, vertically, and diagonally. A word can be in the grid either forward or backward, but its letters must be contiguous. Consider the 9 by 9 grid below:

The words "EWOK," "HUTT," "JABBA," "JARJAR," "JEDI," "SKYWALKER," "WATTO", "YODA" are all in the puzzle (and are shaded).

ERAU has had complaints that some of the words they think are in the puzzle can't be found, so they want to find a way to speed up the verification of the puzzles they create. Your job is to write a program to verify the list of words that ERAU has created that can be found in a search puzzle.

Input Format

The input will consist of a number of puzzle descriptions. The first line of a puzzle description will be an integer n, 0 <= n <= 20, being the number of search words. The next n lines will each contain a search word of no more than 80 uppercase letters. The following line will contain two integers separated by white space, r and c, 1 <= r,c <= 20, being respectively the number of rows and the number of columns. The following r lines will each contain c uppercase letters. The last puzzle description has n=0, and should not be processed.

Output Format

The first output line for a puzzle should be "Puzzle number n:" where n is the position of the puzzle in the list (starting at 1). This is followed by a list of the words (one per line) in the word list that cannot be found in the puzzle, in the same order as they are in the word list. If all the words on the list can be found in the puzzle, then "ALL WORDS FOUND" should be output. A blank line should separate each puzzle.s output from the next.

Sample Input

9
SKYWALKER
WATTO
HUTT
JABBA
DARTHVADER
JARJAR
JEDI
YODA
EWOK
9 9
AEIOUBCHR
JEDIODUFE
AAGHJTKLK
RQBPTNTML
JRSBTVWAA
AYZKAZYXW
RXOWVADOY
TWSRQPNMK
EDFGHJKLS
2
ADD
BAD
4 4
AADD
BBBB
CCCA
DDDD
3
HELLO
GOODBYE
NOTFOUND
5 10
NEXTLINEBA
UOYOLLEHKC
GOODBYEFOR
NOWWASTHIS
FUNFORYOUQ
0

Sample Output

Puzzle number 1:
DARTHVADER

Puzzle number 2:
ALL WORDS FOUND

Puzzle number 3:
NOTFOUND