Group Names by Last Initial

You are given a list of full names, where each name consists of a first name and a last name separated by a space. Your task is to group these names by the initial letter of their last names and output the result as a JSON-formatted dictionary. The dictionary keys should be the single uppercase letter (i.e. the first character of the last name), and the corresponding value should be a list of all names with that last initial, sorted in lexicographical order.

For example, if the input list is:
John Smith, Jane Doe, Alice Johnson, Chris Doe, Bob Doe
the output should be:
{"D": ["Bob Doe", "Chris Doe", "Jane Doe"], "J": ["Alice Johnson"], "S": ["John Smith"]}

When no names are provided, output an empty dictionary {}.

Note that in your solution you should use stdin for input and stdout for output.

inputFormat

The first line of input contains an integer N representing the number of names. The following N lines each contain a full name (first name and last name separated by a space).

outputFormat

Output a JSON-formatted dictionary where the keys are the starting letter of the last names and the values are lists of names (sorted in lexicographical order) that have that last initial. The dictionary itself should have its keys sorted in alphabetical order.## sample

5
John Smith
Jane Doe
Alice Johnson
Chris Doe
Bob Doe

{"D": ["Bob Doe", "Chris Doe", "Jane Doe"], "J": ["Alice Johnson"], "S": ["John Smith"]}