Top K Frequent Words

Given a list of words and a positive integer \(k\), your task is to find the \(k\) most frequent words from the list.

The words should be ordered by decreasing frequency. In the event of a tie where two or more words have the same frequency, the words should appear in lexicographical order (i.e. dictionary order).

Input Format:

The first line of input contains two space-separated integers \(n\) and \(k\), where \(n\) is the number of words. The following \(n\) lines each contain a single word.

Output Format:

Output the \(k\) most frequent words, each on a separate line, following the ordering rules described.

inputFormat

The input begins with a line containing two integers \(n\) and \(k\). \(n\) is the total number of words and \(k\) denotes the number of top frequent words to output. The next \(n\) lines each contain one word.

For example:

6 2
apple
banana
apple
orange
banana
banana

outputFormat

Output exactly \(k\) lines. Each line should contain one word representing the \(k\) most frequent words in order (first by decreasing frequency and then lexicographically for ties).

For the above input, the expected output is:

banana
apple

## sample

3 2
apple
banana
cherry

apple
banana

</p>