Counting Hashtags

Time limit2sMemory limit1024 MB

Summary

Count the distinct hashtags in a text, where a hashtag is a space-separated word that starts with # and has no other #, then print each with its occurrence count.

Level: Easy3 of 10
Topics: Hash map, String
Solved: No attempts yet

Problem

Dima is developing a new trendy social network. He wants to write a module that processes text and counts the distinct hashtags in it.

The text consists of lowercase English letters, digits, the character #, and spaces. A word is a run of consecutive non-space characters bounded on the left and right by spaces or by the start or end of the text. A word is a hashtag if its length is at least $2$ , its first character is #, and none of its other characters is #.

Dima wants to count the distinct hashtags that occur in the text, print them, and print how many times each one occurs.

Input

A single line contains the text in the format described above. The length of the text does not exceed $100\,000$ . The text may contain several spaces in a row, and spaces at the beginning or end of the line.

Output

The first line contains the integer $n$ , the number of distinct hashtags in the text. The next $n$ lines contain a hashtag and the number of times it occurs. The hashtags may be printed in any order.

Examples3

Example 1

Input

i have brought #peace #freedom #justice and #security to my new empire

Expected output

4
#freedom 1
#justice 1
#peace 1
#security 1

Example 2

Input

#to #be #or #not #to #be

Expected output

4
#be 2
#not 1
#or 1
#to 2

Example 3
Input
```
#ioip# #2021 #03#28
```
Expected output
```
1
#2021 1
```