You are given a list of transactions, each of them includes transaction code, product code, selling price, and quantity.

For each product, you have to find out the selling price at which the revenue is the highest. If there are more than one product that have the same highest revenue, print the lowest price.

Input

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

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

Output

• For each product, output the product code and the required selling price and the highest revenue. The list of products should be sorted in ascending order of product code

Sample Input

5
1111 1 1000 5
1112 2 100 1
1113 1 500 10
1114 2 99 1
1115 3 100 2

Sample Output

1 500 5000
2 100 100
3 100 200