Longest Word in Dictionary

Given a string S and a list of strings D, find the longest word in D that can be formed by deleting some characters of S without changing the order of the remaining characters. If there are multiple results of the same length, return the lexicographically smallest one. If no word in D can be formed, return an empty string.

Note: A string x is a subsequence of S if we can remove some (or none) of the characters from S to get x without reordering the remaining characters.

The problem can be mathematically described as follows:

Given a string \( S \) and a set of words \( D = \{w_1, w_2, \ldots, w_k\} \), determine the word \( w \) such that

[ w = \operatorname{arg\ max}_{w_i \in D \text{ and } w_i \text{ is a subsequence of } S} ; (|w_i|, -w_i) ]

where \(|w_i|\) denotes the length of the word and \(-w_i\) implies the lexicographical order is used as a tie-breaker (i.e. the smallest lexicographical order is preferred if lengths are equal).

inputFormat

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

S
n
word_1
word_2
...
word_n

Where:

• S is the reference string.
• n is an integer representing the number of words in the list D.
• word_1, word_2, ..., word_n are the words in the list D, one per line.

outputFormat

Output the longest word from D that is a subsequence of S on a single line to standard output (stdout). If there is no such word, output an empty string.

## sample

abpcplea
4
ale
apple
monkey
plea

apple