Longest Word in Dictionary through Deleting

Given a string \( s \) and a list of words, your task is to find the longest word that can be formed by deleting some characters of \( s \) without changing the order of the remaining characters. If there are multiple possible answers, return the lexicographically smallest one. If no such word exists, output an empty string.

Example:

Input:
abpcplea
4
ale
apple
monkey
plea
Output:
apple

</p>

In the above example, "apple" is the longest word that can be formed from "abpcplea" by deleting some characters.

inputFormat

The input consists of multiple lines:

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

outputFormat

Output a single line containing the longest word from the dictionary that can be formed from \( s \) by deleting some characters. If no valid word exists, print an empty string.

## sample

abpcplea
4
ale
apple
monkey
plea

apple