11825번 - T9 다국어

Many mobile phone users use T9 mode while typing SMS. For example, they type the messages in English in the following way. To type a word by letters, the button corresponding to that letter is pressed only once, no matter how many letters correspond to this button, and no matter which is the position of the letter on this button (see figure), and the software in the phone chooses a word corresponding to the button sequence from the dictionary. If there are several suitable words, then the most frequently occuring word will be offerred first (initially the words with equal frequency are ordered alphabetically). 

If the word is wrong, the user presses button ‘*’ and the software offers the next word by frequency also suitable for the pressed buttons combination, starting from the next word with the same frequency, if any. If it is also wrong, the button ‘*’ will be pressed again etc. For the simplicity we will assume that modern phones contain the full dictionary of the needed words, and the neccessary word will always be found. When the offered word is correct, the user may press “space”, may press the button ‘1’ which corresponds to the punctuation mark or may finish the typing. When the punctuation mark is wrong, the button ‘*’ is pressed also, until the correct character appears. After typing a space or a punctuation mark, the user is allowed to type another space/punctuation mark, is allowed to finish the typing or to start typing the next word. We will assume that three punctuation marks are enough and they are offered in the following order: point (‘.’), comma (‘,’), question mark (‘?’). 

After the user accepts the word (by pressing space or ‘1’), its frequency in the dictionary is increased by 1 and the new frequency value will be taken into account during typing further words of the message. Also, this word will be the first offered word among all the words of the same frequency, but the order of other words will not be changed. When another word with the same frequency appears, then it will be offered first among the words of this frequency, not changing the order of other words, etc. 

You need to write a program which, given a dictionary with initial frequencies of the words and given a sequence of button presses, will write the message that appears on the screen. 

The first line of the input file contains an integer N (3 ≤ N ≤ 50000) — the number of words in the dictionary. Each of the next N lines contains one dictionary word and an integer F (1 ≤ F ≤ 1000) — the initial value of this word frequency (larger value corresponds to larger frequency). The value of the frequency is separated by exactly one space character from the word itself. Dictionary words contain only small english letters. The words in the input file are ordered alphabetically. The word length does not exceed 20 characters, all words are non-empty and different. 

Last line of the input file contains string, denoting the sequence of pressed buttons when message is typed, which consists of digits from 1 to 9, and characters “space” and ‘*’. Length of this line does not exceed 100000 characters. 

Output the text of SMS. 

In the second example, at first the software will propose the word “act”, then “bat”, which will be accepted by the user. Then the frequency of the word “bat” becomes 2. Thus, when the same combination of digits is entered again, the first proposed word is “bat”, then “act” and then “cat”. Third time the words will be proposed in the following order: “cat” (as the new word with frequency 2), “bat” (frequency 2), “act” (and its frequency becomes equal to the frequency of other words), and in the last case the words will be proposed in order “act”, “cat”, “bat”.