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

Your task is to write a program to print the products with the highest revenue day from minimum date to maximum date (Note: print all days from minimum date to maximum date).

If there is more than one product with the same highest revenue, print them too. For any date that has no transaction, print date, product code as ~0~ and selling price as ~0~.

Input

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

• Each line in the next ~N~ lines contains ~4~ integers representing a transaction. All of these do not exceed ~10^9~, the difference between the maximum date and the minimum date is not more than ~10^5~. Dates are in ascending order.

  Output

• For each row, output the date, product code and its revenue. Dates are listed in ascending order; product codes are listed in ascending order.

Sample Input

8
10 1 20 200
10 2 10 150
12 3 18 100
14 2 20 180
14 4 30 80
14 3 40 90
16 4 15 90
16 1 10 180

Sample Output

10 1 4000
11 0 0
12 3 1800
13 0 0
14 2 3600
14 3 3600
15 0 0
16 1 1800