Top K Frequent Words

You are given a dictionary of words with their corresponding frequency counts. Your task is to output the k most frequent words. In case two words have the same frequency, the word that is lexicographically smaller should appear first.

The problem can be formulated as follows:

Given a dictionary \(D\) where \(D(w)\) represents the frequency of word \(w\), and an integer \(k\), return a list of \(k\) words sorted primarily by descending frequency and secondarily by lexicographical order (ascending) when frequencies are equal.

Note: The input and output will be managed via standard input (stdin) and standard output (stdout), respectively.

inputFormat

The first line contains an integer \(n\) which is the number of words in the dictionary. Each of the next \(n\) lines contains a word and its frequency (an integer) separated by a space. The last line contains an integer \(k\), representing the number of top frequent words to output.

Example:

5
apple 5
banana 3
orange 5
grape 3
fig 2
3

outputFormat

Output \(k\) lines, each containing one word. The words should be ordered by descending frequency; if multiple words share the same frequency, they should be sorted in ascending lexicographical order.

Example:

apple
orange
banana

## sample

5
apple 5
banana 3
orange 5
grape 3
fig 2
3

apple
orange
banana

</p>