Longest Concatenation Formation

Given a list of candidate strings and a dictionary of words, your task is to determine the longest candidate string that can be formed by concatenating words from the dictionary. A candidate string is considered valid if it can be segmented into one or more words exactly matching those in the dictionary. In this problem, each word in the dictionary may be used repeatedly.

For instance, the candidate string \(aapplebanana\) can be formed from the dictionary [\(a\), \(apple\), \(banana\)] as follows: \(a + apple + banana\). If no candidate string can be formed using the dictionary, output an empty string.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer \(N\), representing the number of candidate strings. The next \(N\) lines each contain one candidate string. The following line contains an integer \(M\), the number of words in the dictionary, and the next \(M\) lines each contain a single dictionary word.

outputFormat

Print to standard output (stdout) a single line containing the longest candidate string that can be formed by concatenating words from the dictionary. If no such candidate string exists, print an empty string.

4
appleapp
bananaapple
aapplebanana
banana
7
a
banana
app
appl
ap
apply
apple

aapplebanana