EIU Programming Practices and Exams

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 £ N, M £ 10⁵).

-          Each line in the next N lines represents 2 integers: student ID (sID) and class ID (cID) (1 £ sID, cID £ 10⁹).

-          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¹⁸.

Output

The required sorted list. The output should be starting with class ID₁ followed by its attendance list, class ID₂, 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