Twitter shows trends in order to make its users aware of the trending news. These trends are nothing but trending hashtags that the users are tweeting about. For example: If thousands of users are talking about United States by adding a hashtag #US in their tweet, then US will be a trending hashtag. Couple of example tweets with hashtag #US could be:
Given a list of N tweets, your task is to find top the five trending hashtags. Each tweet, let's call it S, will contain at least one one word with hashtag. There will be maximum of three hashtags in any tweet. All hashtags in a single tweet will be unique.
Input:
First line of the input will contain N denoting the number of tweets.
Next N lines, each will contain a string S.
Output:
Print the top five trending hashtags. In case of tie between any two hashtags, print them in lexicographical order in a new line.
Constraints:
Note:
In the given sample test case, the count of occurrences of all the hashtags are:
#US
: 2
#Mars
: 2
#RogerFederer
: 3
#ProximaB
: 3
#Nadal
: 1
#GravitationalWaves
: 1
Sort them by count and in case of tie in count we sort them in lexicographical order of hashtag. It means that Since #RogerFederer
and #ProximaB
has equal count, we compare the strings and since #ProximaB
is lexicographically smaller than #RogerFederer
, #ProximaB
will have precedence over #RogerFederer
.
Final sorted order is:
#ProximaB
: 3
#RogerFederer
: 3
#Mars
: 2
#US
: 2
#GravitationalWaves
: 1
#Nadal
: 1
Top 5 hashtags from the above list is the correct output.