Book Sales Ranking

Problem Description

A bookstore needs to generate a bestseller ranking from its sales data. Each book has a title, sales volume, price, and publication year.

The sorting rules are as follows:

• Sort by sales volume from high to low.
• If sales are equal, sort by price from high to low.
• If price is also equal, sort by publication year from new to old.
• If the year is also equal, sort by title in ascending lexicographic order.

You only need to output the top $k$ books.

Input Format

The first line contains two integers $n$ and $k$, representing the number of books and the number of ranks to output.

The next $n$ lines each contain: title, sales volume, price, publication year. The title contains no spaces.

Output Format

Output $k$ lines, each in the format: rank title sales price year. The rank starts from $1$ and increments by one each line.

Sample Input

6 3
CppPrimer 120 99 2013
PythonGuide 150 80 2020
AlgoBook 150 75 2019
DataStruct 120 99 2011
JavaNote 200 60 2018
OSConcept 150 75 2021

Sample Output

1 JavaNote 200 60 2018
2 PythonGuide 150 80 2020
3 OSCConcept 150 75 2021

Sample Explanation

There are $6$ books in total and we need the top $3$. By the sorting rules, JavaNote has the highest sales (200), so it ranks 1st. Among the books with sales 150 (PythonGuide, AlgoBook, OSCConcept), PythonGuide has the highest price (80 vs 75), so it ranks 2nd. Of the remaining two, OSCConcept was published in 2021 and AlgoBook in 2019, so newer comes first and OSCConcept ranks 3rd. Thus the top 3 are JavaNote, PythonGuide, OSCConcept, matching the sample output.

Constraints

• $1 \le k \le n \le 10^5$
• Sales volume is a non-negative integer not exceeding $10^9$
• Price is a non-negative integer not exceeding $10^9$
• Publication year is an integer between 1900 and 2100
• Titles contain no spaces, have length at most $50$, and are pairwise distinct