Longest Word in Dictionary through Deleting Characters

You are given a string S and a list of words. Your task is to find the longest word in the list that can be formed by deleting some characters of S without changing the order of the remaining characters. In other words, a word w is valid if it is a subsequence of S.

A string w is a subsequence of S if there exists a sequence of indices \(1 \leq i_1 < i_2 < \cdots < i_{|w|} \leq |S|\) such that \(w[j] = S[i_j]\) for all \(1 \leq j \leq |w|\).

If there are multiple possible answers with the same maximum length, choose the one that is smallest in lexicographical order. If no word from the list can be formed, output an empty string.

Example:

Input:
abpcplea
4
ale
apple
monkey
plea
Output:
apple

</p>

inputFormat

The input is given from stdin and follows the format below:

• The first line contains the string S.
• The second line contains an integer n, denoting the number of words in the dictionary.
• The following n lines each contain one word.

outputFormat

Output the longest word from the dictionary that is a subsequence of S to stdout. If there is no such word, output an empty string.

## sample

abpcplea
4
ale
apple
monkey
plea

apple