Longest Word Through Deleting Characters

You are given a string s and an integer n representing the number of words in a dictionary. Then, you are provided with n words. Your task is to find the longest word in the dictionary that can be formed by deleting some characters from s without changing the order of the remaining characters.

If there are multiple valid results, return the word that is smallest in lexicographical order. If no word can be formed, return an empty string.

Note: A word w can be formed from s if all characters of w appear in s in the same order (not necessarily consecutively). In other words, w is a subsequence of s.

Subsequence Check: The word w is a subsequence of s if there exists indices \(1 \leq i_1 < i_2 < \dots < i_{|w|} \leq |s|\) such that \(s_{i_1}=w_1, s_{i_2}=w_2, \dots, s_{i_{|w|}}=w_{|w|}\).

inputFormat

The input is read from stdin and has the following format:

1. The first line contains a string s.
2. The second line contains an integer n, representing the number of words in the dictionary.
3. The following n lines each contain a word from the dictionary.

outputFormat

Output the longest word that can be formed from s by deleting some characters, read from stdin, with the result printed to stdout. If there is no valid word, print an empty string.

abpcplea
3
ale apple monkey

apple