Top K Trending Hashtags

You are given an integer k and a list of tweets. Each tweet is a string that may contain one or more hashtags. A hashtag is defined as a word beginning with the character \(\#\) followed immediately by non-space characters. Your task is to identify the top \(k\) trending hashtags based on their frequency.

The hashtags should be ordered primarily by their frequency in descending order. In the event of a tie (i.e. two or more hashtags occur the same number of times), they should be sorted in lexicographical order (i.e. ASCII order, which effectively means the smaller string comes first).

If there are fewer than \(k\) unique hashtags present, output all the hashtags in the sorted order described above.

inputFormat

The first line contains an integer (k). The following lines each contain a tweet. Each tweet may consist of several tokens separated by spaces, and hashtags are tokens that start with the character '#' (without quotes). The input is provided via standard input (stdin).

outputFormat

Print the top (k) trending hashtags on separate lines, ordered by descending frequency. In cases where multiple hashtags have the same frequency, they should be ordered lexicographically (in ascending order). The output should be written to standard output (stdout).## sample

3
#love #happy #love
#happy #joy
#joy #blessed
#love #happy

#happy
#love
#joy