Longest Subsequence Word

You are given a list of words and a target string. Your task is to find the longest word in the list that is a subsequence of the target string. A word is a subsequence of another string if it can be obtained by deleting some characters (possibly none) from the target without changing the order of the remaining characters.

If there are multiple words of the same maximum length, choose the one which comes first in lexicographical order. If no word in the list is a subsequence of the target, output an empty string.

Recall that for a string s to be a subsequence of another string t, every character in s must appear in t in the same order (not necessarily consecutively). In mathematical terms, if we denote the indices of the characters in s by \(i_1, i_2, \ldots, i_k\), then there exist indices in t such that \[ 0 \leq j_1 < j_2 < \cdots < j_k < |t| \] and for each \(r = 1, 2, \ldots, k\), we have \(s[i_r] = t[j_r]\).

inputFormat

The input is read from standard input (stdin) and has the following format:

1. An integer n, representing the number of words.
2. n lines follow, each containing a single word consisting of lowercase English letters.
3. A single line containing the target string.

For example:

4
apple
plea
monkey
ape
abppplee

outputFormat

Output the longest word from the list that is a subsequence of the target string to standard output (stdout). If no such word exists, output an empty string.

4
apple
plea
monkey
ape
abppplee

apple