Top-K Most Borrowed Books

You are given a series of lending records for books. Each record consists of three integers: book_id, borrow_time, and return_time. Your task is to find the top k books with the highest borrowing counts. In the case where multiple books have the same borrow count, they should be ordered by their book_id in ascending order.

Details:

• The first line of input contains an integer n representing the number of records.
• Each of the following n lines contains three integers: book_id, borrow_time, and return_time.
• The last line of input contains an integer k, indicating the number of top books to output.

The output should list exactly k lines (or fewer if there are not enough distinct books), where each line contains the book_id and its borrow count separated by a space. The books must be sorted first by their borrow counts in descending order and then by their book_id in ascending order.

Mathematically, if we denote the borrow count of book i as \(c_i\), you need to output the books sorted by \(c_i\) in descending order, and if \(c_i=c_j\) then by \(i < j\). That is, sort by \(-c_i\) and then by \(i\).

inputFormat

The input is read from standard input (stdin) and has the following format:

<integer n>
<book_id> <borrow_time> <return_time>
... (n lines)
<integer k>

Here, n is the number of records, followed by n records. The final integer is the number of top books you need to output.

outputFormat

The output should be written to standard output (stdout). For each of the top k books, output a line containing the book_id and its borrow count separated by a space. The ordering should be by descending borrow counts, and for equal counts, by ascending book_id.

## sample

5
101 1 5
102 2 -1
101 6 10
103 3 8
102 11 15
3

101 2
102 2
103 1

</p>