Most Frequent Excluded Word

You are given a string s representing a sentence of space-separated words and a list of banned words. Your task is to determine the most frequent word from s that is not present in the banned list. If there is a tie, return the lexicographically smallest word among the candidates. If no valid word exists, print an empty string.

Note: The input is given via stdin and the output should be printed via stdout.

The problem can be formulated mathematically as follows. Let \( W \) be the multiset of words obtained by splitting the string by spaces and let \( B \) be the set of banned words. We wish to find a word \( w \in W \setminus B \) such that for all other \( w' \in W \setminus B \), either \[ \text{freq}(w) > \text{freq}(w') \quad\text{or}\quad (\text{freq}(w) = \text{freq}(w') \text{ and } w < w') \] where \(w

inputFormat

The input is given through standard input (stdin) in the following format:

S
N
word_1
word_2
...
word_N

Here:

• S is a line containing a sentence with space-separated words.
• N is an integer denoting the number of banned words.
• The following N lines each contain a single banned word.

outputFormat

Output a single line with the most frequent word in S that is not in the banned list. If there is a tie, output the lexicographically smallest one. If no such word exists, output an empty string.

the quick brown fox jumps over the lazy dog quick the fox
2
the
fox

quick