Interessado em fazer um dinheirinho extra, certo professor resolveu passar aos alunos o seguinte exercıcio. Ele deseja montar desafios de palavras cruzadas (que revender´a aos jornais). Para isso, ele monta um tabuleiro e uma lista de palavras que ele deseja que esteja na matriz. A tarefa de vocˆes ´e encontrar um jeito de preencher o tabuleiro com as palavras, se existir. Neste caso o professor poder´a vender o desafio aos jornais (e ficar´a rico).
S˜ao dadas v´arias instˆancias. Cada instˆancia ´e composta pelo n´umero m de linhas e de n colunas do tabuleiro de palavras cruzadas e, a seguir, por m linhas compostas cada uma por n 0’s ou -1’s (o -1 indica uma posi¸c˜ao “preta” e o 0 indica uma posi¸c˜ao branca. Depois do tabuleiro ´e dado o n´umero p de palavras, que seguem nas p linhas seguintes. A entrada termina com uma matriz 0 × 0.
Exemplo: 5 4
-1 0 0 0
0 0 0 0
0 0 -1 0
0 0 0 0
0 -1 0 0
10
ad antas carn casa do lado lua os soda ur
3 3 -1 0
0 0 0 0
0 -1 0 5
ab au bug la lua
0 0
Você deve resolver o seguinte problema:
ab, adido, ai, al, am, atice, banc, bo, boca, cao, dam, dm, enaltecedor, es, et, indo, it, itamaraca, mito, mo, moa, ms, mud, naus, neonato, permitir, remessa, res, robustecida, toast, trem, tri