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 total quantity and total revenue by day from minimum date to maximum date (Note: print all days from minimum date to maximum date).

For any date that has no transaction, print date, total quantity as ~0~ and total revenue 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 day, output the date, total quantity, and total revenue by that day. Dates are listed in ascending order.

Sample Input

8
10 1 20 100
12 2 10 150
12 3 15 100
14 1 15 200
14 2 30 110
15 1 25 90
15 3 25 120
15 1 10 100

Sample Output

10 20 2000
11 0 0
12 25 3000
13 0 0
14 45 6300
15 60 6250