EIU Programming Practices and Exams

Your store has n products, each product has unique identity. Given the cost, the price and the number of items you sold last month for each product, find out the top k highest profit products. Note that if some products have same profit as the k-highest profit product, output them too.

Input

The first line contains two integers n and k (k ≤ n ≤ 10⁵).

Each line in the next n lines contains product’s identity, product’s name, the price, the cost and the quantity you sold.

Note: All integers are less than 2*10^5

Output

The list of top highest profit products which are in order of decreasing the total profit, and increasing identity. Each product output product’s identity, product’s name and the total profit

Sample