After syncing the server log files, Kevin from the IT team now has to go through each log file and count the frequency of the log messages, printing the result in alphabetical order of the log messages. Sounds easy, right? Not for Kevin it seems, as he messed it up again. He managed to incorrectly count the frequency of the log messages and print it out in non-alphabetical order. What a mess!

You've been called in to clean up the mess and perform the frequency analysis properly. Kevin's counting on you (mostly because he doesn't know how to fix it himself).

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 10^5)~, the number of log messages to process.

The next ~n~ lines consist of a string ~M~ ~(1 \leq M.\text{length} \leq 100)~, the log message. The log message will only contain spaces and lowercase and uppercase English characters.

Output

For each log message, output the log messages ~M~ and their frequencies ~f~ in alphabetical order of the messages.

Example

Input 1

6
IT member Kevin accessed the server
IT member Patrick accessed the server
CPU is running hot
All systems OK
IT member Kevin accessed the server
CPU is running hot

Output 1

All systems OK 1
CPU is running hot 2
IT member Kevin accessed the server 2
IT member Patrick accessed the server 1