Group Anagrams

You are given a list of words. Your task is to group the given words into anagrams. Two words are anagrams if they contain the same characters in a different order. For each word, define its key as \(key = sorted(word)\). Then, group the words by their key.

The output should be a JSON object where each key is the sorted string (anagram key) and its value is an array of words (in the order they appeared in the input) that form that group. The keys in the resulting JSON object should be sorted in lexicographical order.

inputFormat

The input is given via standard input (stdin) and it consists of two lines:

• The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)) representing the number of words.
• The second line contains \(n\) words separated by spaces.

outputFormat

Print to standard output (stdout) a JSON object where:

• Each key is the sorted version of the corresponding word (i.e. the anagram key).
• The value for each key is a JSON array of words (in the same order as they appeared in the input) belonging to that anagram group.
• The keys in the JSON object must be sorted in lexicographical order.

7
bat tab eat tea tan nat bat

{"abt":["bat","tab","bat"],"aet":["eat","tea"],"ant":["tan","nat"]}