Merge Collections

You are given several chests, each containing a collection of items. Each item is represented as a pair of strings, where the first string denotes the item name and the second indicates its category. Your task is to merge these collections so that for each category you obtain the list of distinct items.

More formally, if there are \(C\) chests and the \(i\)-th chest contains \(N_i\) items, each specified as a pair \((s, t)\), then you must output a JSON object that maps every category \(t\) to an array of its distinct items \(s\) (sorted lexicographically). The keys (i.e. categories) in the output must also appear in lexicographical order.

inputFormat

The input is read from STDIN. The first line contains an integer \(C\) representing the number of chests. For each chest:

• The first line contains an integer \(N\) denoting the number of items in the chest.
• The next \(N\) lines each contain two space-separated strings: the item name and its category.

outputFormat

Print to STDOUT a JSON string representing an object where each key is a category and its corresponding value is an array of distinct items (sorted lexicographically). The keys must appear in lexicographical order. If there are no chests, output an empty JSON object: {}.

1
3
sword weapon
shield armor
potion potion

{"armor": ["shield"], "potion": ["potion"], "weapon": ["sword"]}