Top Trending Hashtags

You are given one or more datasets containing hashtags along with their frequencies. For each dataset, your task is to determine the top k trending hashtags. The ranking is based on the frequency in descending order, and in case of a tie, lexicographical order (alphabetical) is used.

More formally, for each dataset, you will be given an integer \(n\) (the number of hashtags) and an integer \(k\). Then, \(n\) lines follow, each containing a hashtag (a string) and its frequency (an integer). The hashtags must be sorted primarily by descending frequency and secondarily by ascending lexicographical order. Finally, output the top \(k\) hashtags for each dataset.

The input terminates with a line containing "0 0".

inputFormat

The input is read from the standard input (stdin) and has the following format:

 n k
 hashtag1 frequency1
 hashtag2 frequency2
 ...
 hashtagn frequencyn
 n k
 ...
 0 0

Each dataset starts with two integers \(n\) and \(k\). It is followed by \(n\) lines, each containing a hashtag and its frequency separated by a space. The input terminates when a line with "0 0" is encountered.

outputFormat

For each dataset, output the top \(k\) trending hashtags. Each hashtag should be printed on a separate line to the standard output (stdout). The results of consecutive datasets should be printed continuously.

## sample

5 3
hashtag1 250
hashtag2 500
hashtag3 500
hashtag4 100
hashtag5 300
3 2
tag1 100
tag2 200
tag3 150
0 0

hashtag2
hashtag3
hashtag5
tag2
tag3

</p>