Trending Hashtags

You are given a series of posts and an integer N. Your task is to determine the top N trending hashtags from the posts. A hashtag is defined as any word in the posts that begins with the character #. The popularity of a hashtag is determined by its frequency across all posts. In case of a tie (i.e. two hashtags with the same frequency), the hashtag that is lexicographically smaller (according to standard string order) comes first.

Note: The frequency of a hashtag is the number of times it appears across all posts. For sorting, consider the following order: \[ \text{sort by } (-frequency, \text{lexicographically}) \]

Your program should read the input from standard input (stdin) and print the output to standard output (stdout).

inputFormat

The input is given in the following format:
The first line contains an integer M indicating the number of posts.
The following M lines each contain a post consisting of words and possible hashtags.
The last line contains an integer N, representing the number of top hashtags to output.

outputFormat

Output the top N trending hashtags separated by a single space in one line. If there are no hashtags, output an empty line.

4
#fun #sun #sea
I love the #sea and #sun
#fun and #entertainment
#sea
2

#sea #fun