Anagram Groups

Interview

Time limit1sMemory limit128 MB

Summary

Group distinct words that are anagrams of each other, then print the five largest groups sorted by size and smallest word.

Level: Medium5 of 10
Topics: Hash map, Sorting, String, Implementation
Solved: No attempts yet

Problem

Jun-min wants to divide a list of English words into anagram groups.

A word $w$ is an anagram of a word $v$ if the letters of $w$ can be rearranged to form $v$ . Words that are anagrams of one another form an anagram group. The size of a group is the number of distinct words it contains; if the exact same word appears several times, it is counted only once.

Given the words, write a program that finds the five largest anagram groups.

Input

The input consists of at most 30,000 lines. Each line contains a single word made up of lowercase letters. The input ends at end of file (EOF).

Output

Print up to the five largest anagram groups. If there are fewer than five groups, print all of them.

Print the groups in order of decreasing size. When two groups have the same size, order them by the lexicographically smallest word in each group, in dictionary order.

Print each group on one line in the form Group of size N: w1 w2 ... wk ., where $N$ is the size of the group, followed by the words of the group in dictionary order. Put a single space after each word, and print a single period at the end of the line. Each distinct word is printed only once.

Examples3

Example 1

Input

undisplayed
trace
tea
singleton
eta
eat
displayed
crate
cater
carte
caret
beta
beat
bate
ate
abet

Expected output

Group of size 5: caret carte cater crate trace .
Group of size 4: abet bate beat beta .
Group of size 4: ate eat eta tea .
Group of size 1: displayed .
Group of size 1: singleton .

Example 2
Input
```
hello
```
Expected output
```
Group of size 1: hello .
```

Example 3

Input

abc
bca
cab
abc
xyz

Expected output

Group of size 3: abc bca cab .
Group of size 1: xyz .