Group Anagrams

Given a list of strings strs, place strings that are anagrams into the same group and return those groups.

Two strings qualify as anagrams when each character appears the same number of times in both strings.

Requirements

1. Provide a solution with optimal running time.
2. Evaluate its space usage.
3. Explain an approach for processing datasets that are extremely large.

Input Format

• Line one contains the integer n, representing how many strings follow.
• Each of the following n lines contains one lowercase English string.

Output Format

To make the result deterministic:

• Arrange the strings inside every group in lexicographic order.
• Order the groups according to the first string of each group.
• Output the result as a JSON-like two-dimensional array.

Constraints

• 1 <= n <= 100000
• 0 <= len(strs[i]) <= 100
• The combined character count across all strings does not exceed 1000000.

Example

Input:

6
arc
car
care
acre
robed
bored

Output:

[["acre", "care"], ["arc", "car"], ["bored", "robed"]]

The pairs acre/care, arc/car, and bored/robed each have identical character counts, so they form separate groups. Sorting the strings and then the groups produces the displayed order.

Example

Input:
5
listen
silent
enlist
dog
god

Output: [["dog", "god"], ["enlist", "listen", "silent"]]

Here, dog and god are anagrams, while listen, silent, and enlist share the same letters with the same frequencies. The group beginning with dog comes first lexicographically.