Construct the Last Valid Word

Given a list of words and a string of letters, determine the last word in the list that can be constructed using the letters provided, where each letter in the word must appear no more times than it appears in the given string.

For a word to be valid, let ( f(w, c) ) denote the frequency of character ( c ) in the word and ( f(L, c) ) denote the frequency of ( c ) in the letters string. The word is valid if for every character ( c ) in the word, ( f(w, c) \leq f(L, c) ). If multiple words are valid, output the one that appears last in the list. If no such word can be constructed, output an empty line.

inputFormat

The input is given via standard input (stdin). The first line contains an integer ( n ) indicating the number of words. Each of the following ( n ) lines contains a single word. The last line contains the string of letters.

outputFormat

Output a single line to standard output (stdout) containing the valid word that appears last. If no word can be constructed, output an empty line.## sample

4
apple
orange
banana
grape
elppagorbn

grape