You are given an attendance list of a class. Suppose that there are some students attend all lessons, and every student joinned at least one lessons.

Your task is to write a program to print out student's ID, the number of their absent days and attendant day.

Input

• The first line contains an integer ~M~ – attendance list size ~(1 \leq M \leq 10^5)~.

• Each line in the next ~M~ lines represents ~3~ integers: class's start time (in milliseconds format), student ID and class ID followed by a boolean isCheckin (~0~ - absence or ~1~ - present) . All integers don't exceed ~10^{18}~.

Output

• The required sorted list. Each line in the output contains student ID, the number of their absent days and the number of their attendant day. The list should be sorted in ascending order of student ID.

Sample Input

5
1656894600000 001 0001 1
1656894600000 002 0001 1
1657153800000 001 0001 1
1657499400000 001 0001 1
1657499400000 002 0001 0

Sample Output

001 0 3
002 2 1

Note:

• There is always at least ~1~ student attending all lessons, and every student joinned at least one lessons.