Top Selling Books

You are given a list of books along with their titles, genres, and the number of copies sold. Your task is to output the top K best-selling books for a specified genre.

To solve this problem, you must first filter out the books that do not match the given genre. Then, sort the remaining books in descending order based on the number of copies sold. In the event of ties (i.e. when two books have the same number of copies sold), the order in which they appear in the input should be maintained. If there are fewer than K books in the chosen genre, output all of them. If there are none, output nothing.

Input and Output: Read all input data from standard input (stdin) and write your result to standard output (stdout).

inputFormat

The input begins with a single integer n (1 ≤ n ≤ 10⁵) which denotes the number of books.

This is followed by n lines, each containing a book's details. Each line includes three space-separated fields:

• title – a string (without spaces)
• genre – a string (without spaces)
• copies sold – a non-negative integer

The next line contains a string representing the genre to filter by.

The last line contains an integer K representing the number of top-selling books to output.

outputFormat

Output the titles of the top K best-selling books of the specified genre. Each title should be printed on a separate line. If the number of books available in that genre is less than K, output all available titles. If no books match the genre, do not output anything.

## sample

6
BookA Fiction 150
BookB Non-Fiction 200
BookC Fiction 100
BookD Fiction 300
BookE History 250
BookF Fiction 80
Fiction
2

BookD
BookA

</p>