Sort Genres by Frequency

A library uses an automated system to categorize books based on genres. Each line in the input represents a book record starting with a unique book identifier, followed by one or more genre codes. The system needs to determine the frequency of each genre and output the genres sorted in descending order of frequency. If two genres have the same frequency, they should be output in alphabetical order.

More formally, let \( f(g) \) denote the frequency of a genre \( g \). The genres should be ordered such that for any two genres \( g_1 \) and \( g_2 \):

[ \text{if } f(g_1) > f(g_2) \text{ then } g_1 \text{ comes before } g_2, ] [ \text{if } f(g_1) = f(g_2) \text{ then } g_1 \text{ comes before } g_2 \text{ if } g_1 \text{ is lexicographically smaller than } g_2. ]

The input is read from stdin and consists of several lines. The last line contains only "-1" and should not be processed.

inputFormat

The input consists of multiple lines. Each line (except the last) contains a book record formatted as follows:

BookID Genre1 Genre2 ... GenreN

The final line of the input is "-1" which signals the end of the input. You should not process this line.

outputFormat

Output a single line containing the genres sorted in the required order separated by a single space. If there are no books provided (i.e. the input only contains "-1"), output an empty string.

B1 Fiction Mystery
B2 Fiction Romance
B3 Nonfiction Mystery
B4 Fiction Nonfiction Romance
-1

Fiction Mystery Nonfiction Romance