Longest Word by Deleting Characters

Given a string s and a list of words, 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 results of the same length, return the one that appears first in the list.

More formally, for a word w to be formable from s, there must exist indices 1 ≤ i₁ < i₂ < ... < i_k ≤ |s| such that:

[ w = s_{i_1}s_{i_2}\cdots s_{i_k} ]

If no word in the list can be formed, output an empty string.

inputFormat

The input is read from stdin and consists of multiple lines:

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

You may assume that all strings consist of lowercase English letters.

outputFormat

Print the longest word that can be formed by deleting some characters of s without reordering the remaining characters. If there are multiple words of the same length, output the one which appears first in the list. If no such word exists, output an empty string.

abpcplea
4
ale
apple
monkey
plea

apple