T9 este un sistem dezvoltat pentru a satisface nevoia de a trimite cât mai rapid
mesaje text (SMS) utilizând telefoane mobile. Un mesaj text consta dintr-o succesiune
de cuvinte terminate prin câte un spatiu. Sistemul T9 este bazat pe un dictionar
stocat în memoria telefonului. Daca utilizam acest sistem, atunci când tastam
un cuvânt este suficient sa apasam pentru fiecare litera o singura tasta. La
actionarea unei taste este afisat primul cuvânt din dictionar care contine,
pe pozitia respectiva, una dintre literele înscrise pe tasta actionata. Cuvântul (daca exista în dictionar) va fi format luând
literele de pe pozitiile corespunzatoare din fiecare cuvânt afisat, în ordine.
Exemplu (vezi exemplul 2)
Secventa de taste2 9 4 duce la aparitia cuvintelor 2 AZI (adica una dintre literele
ABC pe prima pozitie) 9 AZI (adica una dintre literele
WXZY pe pozitia a doua) 4 AZI (adica una dintre literele GHI pe pozitia a treia)
deci cuvântul format va fi AZI.
Fiecare litera a unui cuvânt care nu este în dictionar va fi înlocuita cu un caracter
*. Daca exista mai multe cuvinte care corespund unei anumite secvente de actionari
de taste, va fi afisat primul în ordine alfabetica.
Aranjarea literelor pe tastatura telefonului mobil este urmatoarea:
1
2
3
4
5
6
7
8
9
Spatiu
A B C
D E F
G H I
J K L
M N O
P Q R S
T U V
W X Y Z
Cerinta
Scrieti un program care sa simuleze sistemul T9 pe baza unui dictionar dat.
Date de intrare
Fisierul de intrare sms.in
contine:
sms.in
Semnificatie
M
C1
C2
...
CM
N
T1 T2 ... TN
M
reprezinta numarul de cuvinte din dictionar C1 C2 ...
CM reprezinta cuvintele din dictionar ordonate alfabetic N
-numarul de taste actionate T1 T2
... TN - cifrele înscrise pe cele
N taste actionate
Date de iesire
Fisierul de iesire sms.out
contine pe o singura linie mesajul generat de sistemul T9 în urma apasarii celor
N taste. Mesajul se termina cu caracterul spatiu urmat de sfârsit de linie.
Restrictii
1 <= M <= 100
Cuvintele C1, C2,
... , CM sunt ordonate
alfabetic si sunt scrise cu majuscule
Lungimea oricarui cuvânt este de maxim 100
de litere
1 <= N <= 100
Ti apartine multimii
{1, 2, ..., 9}, pentru orice i
din {1, 2, ..., N}