T9 is a system developed to satisfy rapidly growing
needs for quick sending textual messages (SMS) using mobile phones. It is based
on a dictionary stored in a memory of a mobile phone. While typing words it
is sufficient to press a key for each letter once. The first word from dictionary
that begins with letters corresponding to pressed keys is displayed.
The arrangement of letters on a mobile phone keyboard is given with the following
table:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| SPACE | A B C | D E F | G H I | J K L | M N O | P Q R S | T U V | X Y Z |
A message consists of a sequence of words separated by one space. Write a program that will simulate T9 system based on a given dictionary.
Input data
The first line of input file contains a natural
number M, 1 <=M <=100, the number of words in a dictionary. Next M lines
contain dictionary words, one word in each line. The words are sorted in ascending
order. The words contain only capital letters of English alphabet (A-Z). Length
of each word from dictionary will be 100 or less.
The next, (M+2)th line contains a natural number N, 1 <=N <=100, the number
of presses on a mobile phone keyboard.
The following line contains N natural numbers from set {1,2,...,9}, separated
with one space, the numbers of pressed keys.
Output data
The first and only line of output file should contain a message obtained by T9 system. Each letter of a word which is not in a dictionary should be replaced with a '*' character. If more than one word match a sequence of pressed keys, then the first one should be chosen.
Examples
T9.IN
3
ABC
BBB
DEF
10
2 2 2 1 2 3 1 2 2 2
T9.OUT
ABC ** ABC
T9.IN
4
BOK
GDJE
KAKO
STO
11
2 6 5 1 5 2 5 6 1 7 4
T9.OUT
BOK KAKO **
T9.IN
5
GGTMM
GOTOVO
HITNO
ME
NAZOVI
15
6 2 9 6 8 4 1 6 3 1 4 4 8 6 6
T9.OUT
NAZOVI ME GGTMM
