Longest Subsequence Word

Given a target string \(W\) and a list of words, your task is to find the longest word from the list that is a subsequence of \(W\). A word is a subsequence of \(W\) if all its characters appear in \(W\) in the same order, but not necessarily consecutively. If there are multiple words with the maximum length, choose the one that is lexicographically smallest. If no word in the list is a subsequence of \(W\), output an empty string.

inputFormat

The input is read from stdin and consists of:

• The first line contains a non-empty string \(W\).
• The second line contains an integer \(n\) denoting the number of words.
• This is followed by \(n\) lines, each containing one word.

You need to determine the longest word in the list that is a subsequence of \(W\>.

outputFormat

Output to stdout a single string representing the longest word which is a subsequence of \(W\). If no such word exists, output an empty string.

abpcplea
4
ale
apple
monkey
plea

apple