T9

Interview

Time limit1sMemory limit128 MB

Summary
Simulate a T9 keypad predictor that maps key-press sequences to dictionary words, splitting on key 1 as space and marking unmatched words with asterisks.
Level

Medium5 of 10

Topics
String, Hash map, Implementation
Solved
No attempts yet

Problem

T9 is a system developed to satisfy the rapidly growing need to quickly send text messages (SMS) on mobile phones. It works from a dictionary stored in the phone's memory. While typing a word it is enough to press one key for each letter. The first word in the dictionary that matches the letters corresponding to the pressed keys is then displayed.

The arrangement of letters on a mobile phone keypad is given in the following table.

123456789
spaceA B CD E FG H IJ K LM N OP Q R ST U VW X Y Z

A message is a sequence of words separated by single spaces. Write a program that simulates the T9 system for a given dictionary.

Input

The first line contains a natural number M (1 ≤ M ≤ 100), the number of words in the dictionary. Each of the next M lines contains one dictionary word. The words are sorted in ascending order. Each word consists only of capital letters of the English alphabet (A–Z) and has length at most 100.

The (M+2)-th line contains a natural number N (1 ≤ N ≤ 100), the number of key presses.

The following line contains N natural numbers from the set {1, 2, …, 9}, separated by single spaces, the numbers of the pressed keys.

Output

Print the message produced by the T9 system on a single line. Each letter of a word that is not in the dictionary is replaced by a * character. If more than one word matches a sequence of pressed keys, the first such word is chosen.

Examples4

  1. Example 1

    Input
    3
ABC
BBB
DEF
10
2 2 2 1 2 3 1 2 2 2
    Expected output
    ABC ** ABC

  2. Example 2

    Input
    4
BOK
GDJE
KAKO
STO
11
2 6 5 1 5 2 5 6 1 7 4
    Expected output
    BOK KAKO **

  3. Example 3

    Input
    5
GGTMM
GOTOVO
HITNO
ME
NAZOVI
15
6 2 9 6 8 4 1 6 3 1 4 4 8 6 6
    Expected output
    NAZOVI ME GGTMM

  4. Example 4

    Input
    2
HELLO
WORLD
5
4 3 5 5 6
    Expected output
    HELLO