Longest Word in List

You are given a string s and a list of words. Your task is to find the longest word from the list that can be obtained by deleting some characters from s without reordering the remaining characters. If more than one word qualifies, choose the one with the greatest length. If several words have the same maximum length, select the one that appears earliest in the list.

A word w is a subsequence of s if it can be derived from s by deleting zero or more characters without changing the order of the remaining characters. Formally, w is a subsequence of s if there exists a sequence of indices \(1 \leq i_1 < i_2 < \cdots < i_{\lvert w \rvert} \leq \lvert s \rvert\) such that \(w_j = s_{i_j}\) for every \(1 \leq j \leq \lvert w \rvert\).

Note: It is guaranteed that at least one word in the list can be formed from s.

inputFormat

The input is read from the standard input (stdin) and is formatted as follows:

1. A single line containing the string s.
2. A single line containing an integer n representing the number of words in the list.
3. n lines follow, each containing one word.

outputFormat

Output the longest word from the list that is a subsequence of s to the standard output (stdout). If multiple words of the same maximum length exist, output the one that appears first in the list.

abpcplea
3
apple
monkey
plea

apple