Top K Frequent Words

You are given an integer \(K\) and a list of strings \(S\). Your task is to find the top \(K\) most frequent words that appear in the list of strings. In case of ties, the words should be ordered lexicographically (i.e. dictionary order).

Note: Each string in the list \(S\) may contain several words separated by spaces. The frequency of a word is the total number of its occurrences across all strings.

Example:

Input:
K = 3
S = ["the quick brown fox", "jumps over the lazy dog", "the quick blue fox jumps high"]
Output: the fox jumps

</p>

Here, the appears 3 times; fox, jumps, and quick each appear 2 times. Since we need only the top 3 words and in case of a tie, words are compared lexicographically, the answer is the followed by fox and then jumps.

inputFormat

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

K
N
S[1]
S[2]
...
S[N]

Where:

• K is an integer representing the number of most frequent words to output.
• N is an integer representing the number of strings.
• Each S[i] is a string containing words separated by spaces.

outputFormat

Output the top \(K\) frequent words, separated by a single space, in a single line. If there are fewer than \(K\) unique words, output all the unique words sorted by the rules described.

## sample

3
3
the quick brown fox
jumps over the lazy dog
the quick blue fox jumps high

the fox jumps