Most Frequent Borrowed Genres

In this problem, you are given a set of loan records and a mapping from ISBN numbers to book genres. Each loan record contains an ISBN, a borrower ID, and a borrow date. Your goal is to determine, for each borrower, the genres they have borrowed most frequently. If there is a tie, output all the genres with the highest frequency sorted lexicographically.

The problem can be formulated as follows: Given two pieces of data – one representing the loan records and the other a mapping $\text{ISBN} \to \text{Genre}$ – compute for each borrower the set $${g : g \text{ is the most frequent genre borrowed}}.$$

inputFormat

The input is provided via standard input (stdin) and has the following format:

Line 1: An integer $N$, the number of loan records. Next $N$ lines: Each line contains three space-separated strings: ISBN, borrower_id, and borrow_date. Next line: An integer $M$, the number of ISBN-to-genre mappings. Next $M$ lines: Each line contains an ISBN and its corresponding genre.

For example:

5 12345 A1 2023-01-15 67890 A1 2023-02-03 54321 A2 2023-01-10 12345 A1 2023-03-05 67890 A2 2023-02-10 3 12345 Fiction 67890 Science 54321 Fiction

outputFormat

For each unique borrower ID, output a single line in the following format:

borrower_id: genre1 genre2 ...

Here, the genres listed are those the borrower has borrowed most frequently, sorted in lexicographical order. The borrower IDs should also appear in lexicographical order. If there are no loan records, output nothing.## sample

5
12345 A1 2023-01-15
67890 A1 2023-02-03
54321 A2 2023-01-10
12345 A1 2023-03-05
67890 A2 2023-02-10
3
12345 Fiction
67890 Science
54321 Fiction

A1: Fiction
A2: Fiction Science