Top Rated Books by Genre

You are given a list of books. Each book is described by its title, genre, and rating. Your task is to determine the top-rated books for each genre.

For each genre, sort the books by their rating in non-increasing order. If two books have the same rating, sort them by their title in lexicographical order (i.e. alphabetically). Then, select the top k books within that genre (if the genre has less than k books, select all of them).

The input is provided via standard input and the output should be printed on standard output. The output for each genre should be printed on a new line in the following format:

$$\texttt{Genre: Book1 Book2 ...}$$

where the genres are printed in lexicographically increasing order.

inputFormat

The first line of input contains two integers n and k separated by a space, where n is the number of books and k indicates the maximum number of top-rated books to select per genre.

Each of the next n lines contains the information for a single book in the following format:

Title Genre Rating

All fields are separated by spaces. The Rating is an integer.

outputFormat

For each genre (in lexicographically increasing order), print a line with the following format:

Genre: Title1 Title2 ...

Here, the book titles are listed in order of descending rating (and if ratings are equal, in alphabetical order). Only the top k books per genre should be printed. If a genre has fewer than k books, print all of them.

## sample

6 2
MysteryNovel Mystery 5
ScienceBook1 Science 4
ScienceBook2 Science 3
FictionBook1 Fiction 5
FictionBook2 Fiction 4
NonFictionBook NonFiction 5

Fiction: FictionBook1 FictionBook2
Mystery: MysteryNovel
NonFiction: NonFictionBook
Science: ScienceBook1 ScienceBook2

</p>