Top K Frequent Network Requests

You are given a list of network requests. Your task is to determine the top k most frequent requests. The result should be ordered by descending frequency. In case of ties (i.e. two requests with the same frequency), they should be sorted in lexicographical (alphabetical) order.

Formally, if a request appears f times and another request also appears f times, then the one whose string is lexicographically smaller should appear first. If the total number of distinct requests is less than k, output all the distinct requests following the rules above.

For example, if we have 7 requests and we need the top 3, and the requests are:

google.com
facebook.com
google.com
yahoo.com
google.com
facebook.com
bing.com

Then the answer is:

google.com
facebook.com
bing.com

Note that although "yahoo.com" appears once and "bing.com" appears once, lexicographical order places "bing.com" ahead of "yahoo.com".

The solution may involve counting the frequency of each request and then sorting them according to the rules mentioned above. In mathematical terms, if we denote the frequency of request s as \( f(s) \), then we require the sorted order to satisfy:

\[ \text{For two requests } s \text{ and } t, \text{ if } f(s) > f(t) \text{ then } s \text{ precedes } t. \text{ If } f(s) = f(t), \text{ then } s \text{ precedes } t \text{ if } s < t \ (lexicographically). \]

inputFormat

The input is given via standard input (stdin). The first line contains two integers n and k separated by a space where n is the number of network requests and k is the number of top frequent requests to output. The following n lines each contain a string representing a network request.

outputFormat

Print the top k network requests, one per line, in descending order of their frequency. If multiple requests have the same frequency, they must be printed in lexicographical order.## sample

1 1
example.com

example.com