Book Recommendation Based on Genre Popularity

You are given a list of books where each book is represented in the format BookName:Genre1,Genre2,...,GenreM. Additionally, you are provided with a ranking for different literary genres. The task is to recommend the top K books based on the cumulative popularity score of their genres.

For each book, the cumulative popularity score is calculated using the formula:

\( Score = \sum_{i=1}^{m} rank(Genre_i) \)

If a genre from the book is not found in the provided ranking dictionary, its contribution to the score is 0. In case of a tie in cumulative scores, the books should retain their original input order.

You need to take the input from stdin and output the recommended book names to stdout (one per line).

inputFormat

The input is given in the following format:

1. An integer N representing the number of books.
2. N lines each containing a book description in the format BookName:Genre1,Genre2,...,GenreM.
3. An integer R representing the number of genres with provided rankings.
4. R lines each containing a genre and its ranking separated by a space.
5. An integer K that indicates the number of top books to recommend.

outputFormat

Output exactly K lines, each containing the name of one recommended book in order from highest to lowest cumulative score.

## sample

4
Book1:Fantasy,Mystery
Book2:Science Fiction,Fantasy
Book3:Horror,Thriller
Book4:Romance,Mystery
6
Fantasy 10
Mystery 8
Science Fiction 9
Horror 7
Thriller 6
Romance 5
2

Book2
Book1

</p>