Longest Word from Subsequence

You are given a string S and a dictionary of n words. Your task is to find the longest word in the dictionary that can be formed by deleting some of the characters of S without changing the order of the remaining characters.

If there are multiple words with the same maximum length, choose the one that appears first in the input order.

Note: A word w is a subsequence of S if w can be derived from S by deleting zero or more characters without changing the order of the remaining characters. In mathematical terms, if S = s_1 s_2 \dots s_m and w = w_1 w_2 \dots w_k, then there exist indices 1 \leq i_1 < i_2 < \dots < i_k \leq m such that w_j = s_{i_j} for all j=1,2,...,k.

The input is received from standard input and the output should be written to standard output.

inputFormat

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

n
S
word1
word2
... 
wordn

Where n is an integer representing the number of words in the dictionary, S is the main string, and each of the following n lines contains a word from the dictionary.

outputFormat

Output a single line that contains the longest word from the dictionary that can be obtained by deleting some characters of S. If there are multiple answers, output the one that appears first in the input order. If no word can be formed, output an empty string.

5
abcde
a
b
c
ab
cd

ab