Problema B - Inteligência

Os telemóveis modernos ajudam a compor mensagens SMS “inteligentes”. Em vez de escrevermos as palavras exactamente, o que é um bocado fastidioso, pois para representar algumas letras é preciso repetir a mesma tecla várias vezes (por exemplo, para escrever “r” temos de carregar três vezes na tecla “7”), escrevemos “inteligentemente”, algarismo a algarismo. O telemóvel contém uma lista de palavras e perante cada sequência de algarismos, escolhe, de entre essas palavras, a primeira que é compatível com a sequência de algarismos introduzida.

Vejamos um exemplo: suponhamos que o utilizador quer escrever a palavra “luz”. Sem as SMS inteligentes, isto é, em modo básico, teclaria “555889999”. Em modo inteligente bastaria “589”. Com efeito, o “5” pode significar “l”, “k” ou “j”; o “8” pode significar “t”, “u” ou “v”; o “9” pode significar “w”, “x”, “y” ou “z”. Logo, ao todo, a sequência “589” pode representar 3*3*4 = 48 palavras: “ltw”, “ltx”, ..., “luz”, ..., “jvz”. Sendo “luz” a única destas 48 palavras que está na lista, o telemóvel traduz “589” por “luz”.

A parte aborrecida das SMS inteligentes surge quando queremos escrever uma palavra que não existe. Por exemplo, no meu telemóvel, se eu quiser escrever “obg” (abreviatura de “obrigado”), teclando em modo básico “666224”, obtenho “monach”, que não tem nada a ver com o que eu pretendia. Ora como a palavra “monach” até nem existe, o telemóvel bem podia perceber que afinal eu queria mesmo “obg”.

Pois bem, a sua missão neste problema é escrever um programa para traduzir “inteligentemente” as palavras digitadas pelo utilizador no teclado do telemóvel, de acordo com as seguintes regras, que são mais inteligentes do que as regras habituais:

1. Cada mensagem é composta apenas pelos caracteres “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8” e “9”.
2. A tecla “2” representa as letras “a”, “b” e “c”; a tecla “3” representa as letras “d”, “e” e “f”; a tecla “4” representa as letras “g”, “h” e “i”; a tecla “5” representa as letras “j”, “k” e “l”; a tecla “6” representa as letras “m”, “n” e “o”; a tecla “7” representa as letras “p”, “q”, “r” e “s”; a tecla “8” representa as letras “t”, “u” e “v”; a tecla “9” representa as letras “w”, “x”, “y” e “z”.
3. Uma palavra que seja formada só por algarismos de “2” a “9” é traduzida por uma das palavras compatíveis presentes na lista de palavras do telemóvel, se existir pelo menos uma palavra nessas condições, ou então, se não existir, é traduzida usando as regras básicas.
4. Uma sequência de “1” funciona como separador de palavras, sendo traduzido por um único espaço.
5. No caso de haver várias palavras compatíveis na aplicação da regra 3, o número de “1” indica a ordem da palavra que deve ser usada. (Veja os exemplos a seguir). Se o número de “1” for em excesso (isto é, se houver mais “1” do que palavras compatíveis), usa-se a última palavra compatível.
6. Em modo básico (isto é, quando a não há nenhuma palavra compatível com a sequência introduzida), caracteres seguidos iguais em excesso são ignorados. Por exemplo, “22222” é o mesmo do que “222” e representa a letra “c” (e não “ab” ou “ba” ou “aaa”).

Problema

Escreva um programa para traduzir uma mensagem de telemóvel de acordo com as regras anteriores. A mensagem é uma cadeia de caracteres formada por algarismos de “1” a “9”, não começa por “1” e termina sempre por pelo menos um “1”. Esta última sequência de “1” deve ser traduzida não por um espaço mas sim por um ponto “.”.

Input

Na primeira linha vem um número inteiro N, que representa o número de palavras na lista de palavras do telemóvel (0 <= N <= 30000). Nas N linhas seguintes vêm, por ordem alfabética, uma em cada linha, as palavras que fazem parte dessa lista. Todas as palavras são escritas só com letras minúsculas, sem acentos ou cedilhas, e uma palavra não tem mais que 30 letras.

Segue-se uma linha com um número inteiro M (1 <= M <= 1000), que representa o número de mensagens a traduzir. Nas M linhas seguintes vêm essas mensagens, uma em cada linha. Cada mensagem não tem mais do que 1024 caracteres.

Output

Exemplo de Input

6
enunciado
informatica
nacionais
olimpiadas
ter
ver
3
65467423271463676284221
837113686242361
666551831223361

Exemplo de Output

olimpiadas informatica.
ver enunciado.
ok td bem.