EIU Programming Practices and Exams

Duc is investing in the stock market and would like to know well he invests. Note that, every time he makes a transaction with some stock shares, he pays a transaction fee at 0.1% of the total cost. He also pays 0.1% as tax for any sell transaction. Given the list of transactions, output top m stock brings the highest profits to him. It is guaranteed that no shares are left in his account at the end of n transactions.

Input

The first line contains two integer n, m

Each line in the next N lines represents a transaction that starts with the transaction type ‘S’ (sell) or ‘B’ (buy), followed by a string that is stock code. The rest of the line is the number of shares q and the price of each share in the transaction.

Output

Starts with the m highest profits stock. Each line contains the stock code and the profit. The list is in the decreasing order of profit and increasing order of stock code. If two stocks bring the same profits, they should be printed together or none of them are printed.

Example

Input:
10 2
B ACB 500 30000
B FPT 100 40000
B FPT 100 41000
B BCM 500 10000
B BCM 1000 12000
S ACB 100 27000
S ACB 100 40000
S ACB  300 31000
S BCM 1500 30000
S FPT 200 40000


Output:
BCM 27893000
ACB 953000