T9

Many mobile phone users type SMS messages with T9 input. Implement it.

Each digit button carries a group of lowercase English letters.

To type a word, the user presses the button of every letter exactly once, no matter how many letters that button carries and no matter where the letter sits on the button. The software picks a dictionary word that matches the sequence of pressed buttons and shows it on the screen. If several words match, the one with the larger frequency is offered first, and words of equal frequency start out in alphabetical order.

If the offered word is wrong, the user presses *, and the next word for the same button sequence appears. If that one is wrong too, * is pressed again. Assume a modern phone holds a full dictionary of the needed words, so the needed word is always found.

When the offered word is correct, the user may press space, may press 1 for a punctuation mark, or may finish typing. When the offered punctuation mark is wrong, * is pressed until the correct character appears. Three punctuation marks are enough, and they are offered in the order ., ,, ?. After a space or a punctuation mark the user may type another space or punctuation mark, may finish typing, or may start the next word.

After the user accepts a word by pressing space or 1, its frequency in the dictionary grows by 1, and the new value applies to the words typed after it. That word also becomes the first offered word among all words of the same frequency, and the order of the other words does not change. When another word reaches that frequency later, it becomes the first offered word of that frequency, and the order of the remaining words stays as it was.

A button from 2 to 9 is appended to the button sequence of the word being typed. Once the sequence grows, the software starts again from the first candidate of the new sequence. A word or a punctuation mark still on the screen when the typing ends is part of the message, but a word that was not accepted with space or 1 does not gain frequency.

Given the dictionary with the initial frequency of every word and the sequence of pressed buttons, write the message that appears on the screen.

The first line contains the number of dictionary words $N$ ($3 \le N \le 50000$). Each of the next $N$ lines contains one dictionary word and an integer $F$ ($1 \le F \le 1000$), the initial frequency of that word; a larger value means a higher frequency. Exactly one space separates the word from the frequency. Words consist of lowercase English letters only, are at most 20 characters long, are non-empty and are all different. The words are given in alphabetical order.

The last line contains the string of pressed buttons, made of the digits 1 to 9, the space character and *. Its length is at most 100000.

Print the text of the SMS that appears on the screen.

In the second example the software first offers act, then bat, and the user accepts bat. The frequency of bat becomes 2, so entering the same digits again offers bat, then act, then cat. The third time the order is cat (the word that has just reached frequency 2), then bat (frequency 2), then act, whose frequency then matches the other words. In the last case the words are offered in the order act, cat, bat.