You are given a list of transactions. Each transaction includes employee id, number of products and sold price. Sort the given list of employees in descending order of total revenue.

Input

• The first line contains one integer ~N~ - the number of transactions ~(1 \leq N \leq 10^5)~.

• Each line in the next ~N~ lines represents a transaction, contains three integers: ~C_i~, ~Q_i~, and ~P_i~, which are the employee's id, number of products, and price. All integers don't exceed ~10^9~.

Output

• The required sorted list. Each line in the output contains the employee's id and the total revenue.

• If there are employees who have same total revenue, they should be sorted in ascending order of id.

Sample Input

4
1 20 5
2 20 10
1 10 10
3 50 10

Sample Output

3 500
1 200
2 200