Top K Trending Hashtags

In this problem, you are given a list of social media posts. Each post may contain zero or more hashtags, where a hashtag is defined as any substring starting with the character #. When a hashtag appears multiple times in a single post, it should be counted only once for that post. The trending score of a hashtag is defined as the number of posts in which it appears.

Your task is to find the top k trending hashtags from these posts. The hashtags should be sorted primarily by their trending score in descending order and secondarily by the order of their first appearance in the input (i.e. if two hashtags have the same score, the one that appeared in an earlier post comes first).

Formal description:

Given two integers \(n\) and \(k\), followed by \(n\) social media posts, determine the top \(k\) hashtags. If there are fewer than \(k\) hashtags available, output all of them. Each output line must contain the hashtag and its trending score, separated by a space.

inputFormat

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

n k
post_1
post_2
...
post_n

Here, the first line contains two integers: \(n\) (the number of posts) and \(k\) (the number of top trending hashtags to output). The next \(n\) lines each contain one social media post.

outputFormat

For each of the top trending hashtags, output a line containing the hashtag and its trending score separated by a space. If there are no hashtags, output nothing.

## sample

7 3
Enjoying the sunny day #weather #sun
Rainy afternoon, perfect for reading #weather #rain
Good morning! #morning
Lunchtime with colleagues #food
Reading tech news #technology #news
What a beautiful sunset #weather #sunset
Stuck in traffic #commute #traffic

#weather 3
#sun 1
#rain 1

</p>