Problema C - Em busca dos enunciados perdidos

Num futuro não muito longínquo, perdido num templo profundo, escondido numa selva densa, está um achado arqueológico de grande valor: os enunciados dos problemas usados nas primeiras Olimpíadas Portuguesas de Informática!! O seu valor é incalculável e quem poderia estar atrás deste tesouro? Ninguém mais do que Indiana Jones Junior, o descendente do grande caçador de tesouros!

Junior já conseguiu chegar ao templo, mas a separá-lo dos enunciados estão uma série de armadilhas mortais que o desafiam. Neste momento ele tem pela frente um quadriculado de pedras, cada uma com uma letra. Junior sabe que tem de pisar as pedras por uma determinada ordem e tem a certeza que se pisar as letras erradas um dardo mortal será lançado das paredes do templo. O que lhe resta fazer, portanto, é saber que letras "pisar" e por que ordem para passar mais este obstáculo...

O quadriculado de letras é representado por um matriz, e a figura seguinte mostra o cenário que se apresenta ao Indiana.

|I. Jones Junior|
\___        ____/
    |optpag|
    |fnharo|
    |ihmatg|
 ___|sareri|____
/               \
| Caminho para  |
|  Enunciados   |

Junior tem de tem de começar numa pedra qualquer da linha de cima (OPTPAG) e acabar numa pedra qualquer da linha de baixo (SARERI). Em cada passo pode andar para uma das oito casas adjacentes (vertical, horizontal e diagonal). Não pode também passar duas vezes pela mesma pedra (na mesma palavra) sob pena de ser disparado um dardo. Seguindo estas regras, Junior consegue formar as palavras PROGRAMA e ONIS mas não GANHAR:

Optpag    optPag
fNharo    fnhaRO
Ihmatg    ihMAtG
Sareri    sAreRi

Junior não tem a certeza de qual palavra é que deve usar, mas sabendo quais são as palavras possíveis torna-se mais fácil decidir o que fazer. Precavido como é, trouxe um portátil. Serás capaz de o ajudar?

O Problema

A tua tarefa é ajudar o Indiana Jones Junior fazendo um programa que dada uma lista de palavras (o dicionário) e uma matriz de letras (o quadriculado de pedras) diga quais são as palavras que são possíveis de formar começando na linha de cima (em qualquer coluna) e acabando na linha de baixo (também em qualquer coluna). Relembra que em cada passo Junior só pode deslocar-se para uma das 8 casas adjacentes na vertical, horizontal e diagonal e nunca pode repetir a mesma posição.

Input

O input começa por ter uma linha contendo dois números inteiros separados por um espaço, L C (0 < L,C ≤ 20), representando respectivamente o número de linhas e colunas do quadriculado de letras a considerar.

Seguem-se L linhas, cada uma com C letras minúsculas, representando o quadriculado em si.

Depois vem uma linha contendo D (0 < D ≤ 500), o número de palavras do dicionário a considerar, seguida de D linhas, cada uma contendo uma palavra formada por letras minúsculas. As palavras são dadas numa ordem arbitrária e nunca terão um tamanho superior a 100.

Output

A primeira linha de output deve conter um único número indicando o número de palavras do dicionário que é possível formar. Segue-se a lista das palavras propriamente ditas, uma por linha. As palavras devem vir ordenadas por ordem crescente de tamanho (Junior quer cansar-se o mínimo possível) e dentro do mesmo tamanho, devem vir ordenadas por ordem crescente alfabética.

Vê os exemplos para esclarecer qualquer dúvida.

Exemplo de Input 1

4 6
optpag
fnharo
ihmatg
sareri
3
programa
onis
ganhar

Exemplo de Output 1

2
onis
programa

Exemplo de Input 2

3 3
abc
def
ghi
2
dicionario
pequeno

Exemplo de Output 2

0

Exemplo de Input 3

3 4
asut
tomx
lajo
4
uma
ata
sol
sua

Exemplo de Output 3

3
ata
sol
uma