Top K Frequent Words

You are given a list of words with their corresponding frequency counts. Your task is to output the top $K$ frequent words in descending order of frequency. In case two words have the same frequency, they should be sorted in lexicographical (alphabetical) order (ascending).

For instance, if two words both appear 3 times, the word that comes first alphabetically will appear first in the output list. Input is provided via standard input and the output should be written to standard output.

inputFormat

The first line contains two integers $N$ and $K$, where $N$ is the number of words. This is followed by $N$ lines, each containing a word (a string without spaces) and an integer representing its frequency, separated by a space.

outputFormat

Print a single line containing the top $K$ frequent words separated by a single space.## sample

5 3
apple 4
banana 2
orange 5
grape 2
pear 3

orange apple pear