Construct the Longest Message

You are given a list of words and a string s. Your task is to construct a message by selecting, for each character in s, the longest word from the list that starts with that character. If no such word exists for a character, insert an empty string for that position.

The problem can be mathematically formulated as follows: for each character \(c\) in the string \(s\), find the word \(w\) in the list \(W\) such that \(w[0] = c\) and \(\lvert w \rvert = \max\{\lvert x \rvert : x \in W, x[0] = c\}\). The answer is the concatenation of the chosen words separated by a single space. Note that if no word matches a specific character, an empty segment is used in that position, which results in an extra space when joining.

inputFormat

The input is read from standard input (stdin) and is in the following format:

<n>
<word1> <word2> ... <word_n>
<s>

Where \(n\) is the number of words, the next line contains \(n\) words separated by spaces, and the last line contains the string \(s\).

outputFormat

Output a single line to standard output (stdout) containing the constructed message. The message is the concatenation of the selected words (one for each character in \(s\)) separated by a single space. If no word matches a character, an empty part is included which may result in an extra space.

5
apple bear eagle orb racecar
abe

apple bear eagle