Given the list of check-in and check-out time of employees. Output the number of working hours of them.

Input

• The first line contains a number of check-in, check-out records ~(1 \leq N \leq 10^5)~.

• Each line in the next ~N~ lines contains two integers representing a record. First integer is the id of employee. The second integer is the time of check-in/check-out

Output

• The list of employees in ascending order of id. For each employee, output the id and the number of working hours.

Sample Input

6
1 4
2 4
1 5
1 6
2 8
1 11

Sample Output

1 6
2 4