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^{5}~).

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

Note: All integers are less than ~2\times10^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 identity, product name and the total profit

Sample Input

4 2
1 laptop 10 8 3
2 watch 20 17 2
3 phone 100 87 1
4 glasses 10 9 5

Sample Output

3 phone 13
1 laptop 6
2 watch 6