Caça Palavras

Esta tarefa é baseada no popular passatempo Caça-Palavras. Para quem não conhece, o problema pode ser definido da seguinte maneira. Dada uma matriz de caracteres (letras ou números) e uma lista de palavras (letras e números são considerados caracteres válidos para palavras), determinar se as palavras podem ser encontradas na matriz. Uma palavra pode ser escrita se a seqüência de letras da palavra pode ser encontrada na matriz, de tal forma que:

• a primeira letra da palavra existe na matriz;
• cada letra subsequente da palavra existe na matriz em uma posição vizinha à posição da letra corrente, em um dos oito sentidos diferentes (N, NE, L, SE, S, SO, O,NO);
• Uma posição na matriz pode ser utilizada mais de uma vez para formar a palavra.

Para cada palavra, deseja-se saber todas as posições iniciais onde ela pode ser encontrada (caso exista alguma).

Por exemplo, suponha a seguinte matriz:

Segundo a definição do problema, a palavra CASA pode ser encontrada na posição (1, 1) da matriz. A palavra começa no C, segue para a direita passando pelo A e pelo S e finaliza voltando para a esquerda, utilizando novamente o A. Como outro exemplo, a próxima matriz possui a palavra ARARAQUARA na posição (2, 4):

Tarefa

Escreva um programa que resolva o passatempo dado.

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém três números inteiros positivos L, C e P tais que 0 ≤ L, C, P ≤ 50, que indicam respectivamente o número de linhas da matriz de caracteres (0 ≤ L ≤ 50) o número de colunas da matriz de caracteres (0 ≤ C ≤ 50) e o número de palavras a serem procuradas na matriz (0 ≤ C ≤ 50). As L linhas seguintes contêm cada uma C caracteres, representando a matriz. A seguir, são dadas P linhas, cada uma contendo uma palavra a ser procurada na matriz. Cada palavra terá no mínimo 1 e no máximo 50 caracteres. O final da entrada é indicado quando L = C = P = 0.

A leitura deverá ser feita a partir da entrada padrão.

Exemplo de Entrada

8 11 8
abcdefghigg
hebkwaldork
ftyawaldorm
ftsimrlqsrc
byoarbedeyv
klcbqwikomk
strebgadhrb
yuiqlxcnbjf
waldorf
bambi
betty
paralelepipedo
dagbert
frod
rebelde
amarrar
20 20 13
QWSPILAATIRAGRAMYKEI
AGTRCLQAXLPOIJLFVBUQ
TQTKAZXVMRWALEMAPKCW
LIEACNKAZXKPOTPIZCEO
FGKLSTCBTROPICALBLBC
JEWHJEEWSMLPOEKORORA
LUPQWRNJOAAGJKMUSJAE
KRQEIOLOAOQPRTVILCBZ
QOPUCAJSPPOUTMTSLPSF
LPOUYTRFGMMLKIUISXSW
WAHCPOIYTGAKLMNAHBVA
EIAKHPLBGSMCLOGNGJML
LDTIKENVCSWQAZUAOEAL
HOPLPGEJKMNUTIIORMNC
LOIUFTGSQACAXMOPBEIO
QOASDHOPEPNBUYUYOBXB
IONIAELOJHSWASMOUTRK
HPOIYTJPLNAQWDRIBITG
LPOINUYMRTEMPTMLMNBO
PAFCOPLHAVAIANALBPFS
MARGARITA
ALEMA
BARBECUE
TROPICAL
SUPREMA
LOUISIANA
CHEESEHAM
EUROPA
HAVAIANA
CAMPONESA
POTE
TROPICO
MONGOL
0 0 0

Saída

Para cada conjunto de teste da entrada seu programa deve produzir um conjunto de linhas. A primeira linha identifica o conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A seguir, para cada umas das P palavras do conjunto, caso a palavra possa ser encontrada na matriz, deverá ser impressa a seguinte mensagem para cada uma das posições iniciais onde a palavra pode ser lida:

• palavra: linha X, coluna Y

Onde palavra é a palavra em questão, X é o número da linha (1 ≤ X ≤L) e Y é o número da coluna (1 ≤ Y ≤C).

Caso a palavra não possa ser localizada em nenhuma posição da matriz, a seguinte mensagem deve ser impressa:

• palavra: nao encontrada

Observe os exemplos e repare na ordem de impressão quando uma palavra possuir mais de uma ocorrência. A saída deverá ser escrita na saída padrão.

Imprima uma linha em branco após cada caso de teste. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de Saída

Teste 1
waldorf: linha 2, coluna 5
waldorf: linha 3, coluna 5
bambi: linha 2, coluna 3
bambi: linha 6, coluna 4
betty: linha 1, coluna 2
betty: linha 2, coluna 3
paralelepipedo: nao encontrada
dagbert: linha 7, coluna 8
frod: linha 8, coluna 11
rebelde: linha 4, coluna 6
amarrar: linha 3, coluna 4
amarrar: linha 3, coluna 6
amarrar: linha 5, coluna 4

Teste 2
MARGARITA: linha 1, coluna 16
ALEMA: linha 1, coluna 15
ALEMA: linha 3, coluna 12
ALEMA: linha 3, coluna 16
BARBECUE: linha 5, coluna 19
BARBECUE: linha 8, coluna 19
TROPICAL: linha 5, coluna 9
SUPREMA: linha 17, coluna 14
LOUISIANA: linha 5, coluna 16
CHEESEHAM: linha 11, coluna 4
EUROPA: linha 6, coluna 2
HAVAIANA: linha 20, coluna 8
CAMPONESA: linha 12, coluna 12
POTE: linha 4, coluna 12
POTE: linha 5, coluna 12
POTE: linha 16, coluna 8
TROPICO: linha 5, coluna 9
MONGOL: linha 11, coluna 14
MONGOL: linha 14, coluna 18

(esta saída corresponde ao exemplo de entrada acima)