You are given a list of transactions, each of them includes transaction code, product code, selling price, quantity and cost per unit. Your task is to write a program to print top K products which have the highest net income (total revenue – total cost).

Input

• The first line contains two integer ~N~ (the number of transactions) and ~K~ ~(1 ≤ N, K ≤ 10^5)~.

• Each line in the next ~N~ lines contains five integers representing a transaction. All of them do not exceed ~10^9~

Output

• The required list of the products is sorted in descending order of the net income and ascending order of product code.

• For each product, print the product code and the net income. Note that, if there are products that have the same net income as the net income of the ~K^{th}~ product, print them too.

Sample Input

5 2
1111 1 1000 2 400
1112 2 100 1 78
1113 1 500 10 350
1114 2 99 1 85
1115 3 100 2 15

Sample Output

1 2700
3 170