Most Frequent Next Word

You are given a list of sentences and a target word. Your task is to determine the word that most frequently occurs immediately after the target word in all the given sentences. If the target word does not appear in any sentence or if it never has a subsequent word, output an empty string. In the event of a tie (i.e. multiple words have the same maximum frequency following the target word), output the lexicographically smallest word.

Note: When comparing words lexicographically, use the standard dictionary order. All inputs consist of lower-case letters and spaces only.

Hints: You may find it useful to split each sentence into words and then iterate through the word list to count frequencies.

For any word w immediately following the target word, its frequency is counted. Formally, if you denote the frequency of a word v following the target word t as \( f(v) \), then the answer is the word \( v^* \) such that

[ f(v^) = \max_{v} f(v), \quad \text{and if } f(u) = f(v^) \ \text{ for some other } u, \text{ choose } v^* = \min{u, v^*} \text{ lexicographically.} ]

inputFormat

The first line contains an integer T representing the number of sentences. The next T lines each contain a sentence. The final line contains the target word.

Constraints:
1 ≤ T ≤ 1000
Each sentence contains only lowercase letters and spaces.

outputFormat

Output a single line containing the word that most frequently appears immediately after the target word in the given sentences. If no such word exists, output an empty string.

4
hello world
world of coding
hello there world
world world world hello
world

world