Finding the Most Popular Books by Genre

You are given a list of books. Each book has a title, a popularity score, and a list of genres to which it belongs. Your task is to determine the most popular book for each genre. For every genre present among the books, output the title of the book that has the highest popularity. In case two or more books have the same popularity for a genre, choose the one that appears first in the input.

Formally, if each book is represented as a tuple (title, popularity, genres) and for a given genre ( g ), let the books that belong to ( g ) be considered. Then, you must choose the book with the maximum popularity:

[ book(g) = \mathrm{argmax}_{book \in \mathcal{B}_g} (popularity(book)) ]

with ties broken by the order of appearance in the input.

inputFormat

The input is read from standard input (stdin) in the following format:

The first line contains an integer ( n ) representing the number of books.

For each book, there are three lines:

1. The first line contains the title of the book (a string).
2. The second line contains an integer representing the popularity of the book.
3. The third line contains one or more genres (space-separated strings) for the book.

It is guaranteed that ( n \ge 0 ).

outputFormat

Output a JSON object (as a string to stdout) representing a dictionary. Each key in the dictionary is a genre and the corresponding value is the title of the most popular book in that genre. The keys in the JSON output should be sorted in lexicographical order.## sample

5
Book1
80
Mystery Thriller
Book2
150
Sci-Fi
Book3
90
Mystery
Book4
85
Thriller
Book5
95
Sci-Fi Mystery

{"Mystery": "Book5", "Sci-Fi": "Book2", "Thriller": "Book4"}