Problema dos nomes das vacas (USACO)

Tradução de Name That Number da USACO (http://ace.delos.com/usacoprob2?a=pbvbeOWRbRk&S=namenum).

Dificuldade Única

No rebanho do rancho Wisconsin é costume identificar as vacas com um número serial para agradar à contabilidade. O vaqueiro não aprecia este sistema e deseja chamar as vacas da manada por um nome agradável ao invés de dizer, "Hei, #4734, vá em frente".

Ajude o pobre vaqueiro escrevendo um programa que irá traduzir o número serial de identificação de uma vaca em possíveis nomes que só poderiam ser associados àquele número serial. Como estes dias todos os vaqueiros têm um celular na sela, use o mapeamento padrão do teclado Touch-Tone® do telefone para converter os números em letras (exceto "Q" e "Z").

2: A,B,C     5: J,K,L    8: T,U,V
3: D,E,F     6: M,N,O    9: W,X,Y
4: G,H,I     7: P,R,S

Os nomes aceitos para o gado são fornecido pelo arquivo dict.txt, que contem não mais que 5000 nomes (todos em letras maiúsculas). Recebendo o número identificador de uma vaca, informe todos os possíveis mapeamentos que estão contidos no dicionário fornecido (ordenado em ordem alfabética ascendente).

Por exemplo, o número identificador 4734 gera as seguintes possibilidades:

GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI
GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI
GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI
HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI
HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI
IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI
ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI

Acontece que o único nome desdes 81 que está na lista de nomes válidos é "GREG".

Escreva um programa que dado o número identificador de uma vaca, imprima todos os nomes válidos que podem ser gerados a partir do número serial ou "NONE" se não há nome válido que possa ser gerado. Os números seriais podem ter até 12 digitos (inclusive).

Formado de entrada

Uma única linha com os números identificadores com 1 a 12 digitos.

Exemplo de entrada

4734

Nome do arquivo de entrada: namenum.in.

Formato de saída

Uma lista de nomes válidos (um por linha) que podem ser gerados a partir da entrada em ordem alfabética ascendente.

Nome do arquivo de saída: namenum.out.

Exemplo de saída

GREG