Longest Word by Deleting Characters

Given a string \( S \) and a list of words \( L \), your task is to find the longest word in \( L \) that can be formed by deleting some characters of \( S \) without reordering the remaining characters. If multiple words of the same maximum length can be formed, output the one that appears first in the list. If no word can be formed, output an empty string.

More formally, a word \( 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 each \( j \) from \( 1 \) to \( |w| \). You need to check for each word in \( L \) whether it is a subsequence of \( S \) and select the longest one.

Examples:

• Input: S = "abppplee", L = ["able", "ale", "apple", "bale", "kangaroo"]; Output: "apple"
• Input: S = "abcdef", L = ["ghijk", "lmnop", "qrst"]; Output: "" (empty string)
• Input: S = "aaaaaa", L = ["a", "aa", "aaa"]; Output: "aaa"
• Input: S = "abcd", L = ["ab", "cd", "cb", "ad"]; Output: "ab"
• Input: S = "", L = ["a", "b", "c"]; Output: "" (empty string)

inputFormat

The input is given via standard input (stdin) and has the following format:

S
n
word1
word2
...
wordn

Where:

• S is the main string.
• n is an integer representing the number of words in the list.
• The next n lines each contain one word from the list \( L \).

outputFormat

Output the longest word that can be formed from \( S \) as described. If no word can be formed, output an empty string. The output is printed to standard output (stdout).

## sample

abppplee
5
able
ale
apple
bale
kangaroo

apple