Text on 9 Keys
T9, which stands for Text on 9 keys, is a predictive text technology for SMS composition in mobile phones. T9's objective is to make it easier to type text messages on small mobile devices. The technology allows words to be entered by a single keypress for each letter.
With this feature ON, the user can write, for example, the word "concurso" by pressing the keys 26628776 one at a time, in sequence, instead of having to press the 2 key three times (to obtain the letter 'c'), the 6 key 3 times ('o'), the 6 key two times ('n') and so on, until, finally (with his finger already aching), the 6 key three times (to obtain the last 'o').
While in T9 mode, at any time during the
writing of the word "concurso" (for example, after pressing
266), the user may ask to see all words in the mobile phone internal
dictionary beginning with letters that can be obtained with the
sequence already written. For example, after pressing 266, one would
obtain the words "amor", "ano", "boné",
"bobadela", "bom", "bombeiro",
"comando", "combinação", "comer",
"comprar" "concurso", "conselho", etc.
Your friend wants to implement a simplified T9 option in his machine, and you are going to help him. Your task is to find, among a given dictionary, the words that match a given initial sequence of digits between 2 and 9 knowing that the letters that can be obtained from each key are as shown in the following table (notice that your friend is not interested on having any numbers, lowercase letters, nor any characters with accents or diacritical marks as, for example, á, õ, ê, ç, etc):
The first line of the input contains a sequence s
of n digits (n<=20), standing for the keys that are
pressed to write a (part of a) word. The following lines define the
dictionary: each line contains one word (of 20 characters at most).
The dictionary contains a maximum of 10 000 words.
The first line of the output contains the sequence
s. The next lines contain the words in the dictionary, by
ascending lexicographic order, whose first n characters
correspond to the input sequence s (according to the T9
Sample Input 1
737 ANANAS CARAMELO BANANA MACA PAPAIA REQUEIJAO PERA MANGA PERABACATE ROMA
Sample Output 1
737 PERA PERABACATE REQUEIJAO
Sample Input 2
233767 AZINHEIRA CARVALHO CEDRO CEREJEIRA CIPRESTE EUCALIPTO FAIA LARANJEIRA MACIEIRA NOGUEIRA OLIVEIRA PEREIRA PLATANO
Sample Output 2