You are given an attendance list of EIU (multiple classes). Suppose that each class has some students attending all the class's lessons, and every student joinned at least one lessons of overy class that they registered.

Your task is to write a program to print out attendance list of each class.

Input

• The first line contains two integers ~N~ – all class sizes, ~M~ – all attendance list sizes ~(1 \leq N, M \leq 10^5)~.

• Each line in the next ~N~ lines represents ~2~ integers: student ID (sID) and class ID (cID) ~(1 \leq~ sID, cID ~\leq 10^9)~.

• 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. The output should be starting with class ~ID_1~ followed by its attendance list, class ~ID_2~, its attendance list, … Each line in the attendance list 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 class ID, student ID.

Sample Input

4 8
001 0001
002 0001
001 0002
003 0002
1656894600000 001 0001 1
1657153800000 001 0001 1
1657153800000 002 0001 1
1656894600000 001 0002 1
1656894600000 003 0002 1
1657153800000 003 0002 1
1657153800000 001 0002 0
1657758600000 003 0002 1

Sample Output

0001
001 0 2
002 1 1
0002
001 2 1
003 0 3