Parking Lot

Interview

Time limit1sMemory limit1024 MB

Summary

Given timestamped entry and exit records for cars, print each car number and the seconds it stayed, in the order the cars left.

Level: Easy3 of 10
Topics: Hash map, Implementation
Solved: No attempts yet

Statement

Modern parking lots often install systems that record the numbers of cars entering and leaving. This lets the operator charge car owners by the exact time their cars spent in the lot.

This problem covers one component of such a system.

You are given a list of records. Each record consists of two integers:

$T\_i$ : the time moment, in seconds
$N\_i$ : the car number

The first record with a given $N\_i$ means that car entered the lot. The second means that car left. You may assume that no number appears in the list more than twice.

Calculate how long each car stayed in the lot.

Input

The first line contains one integer $M$ , the number of records. The next $M$ lines each contain one record, consisting of the two integers $T\_i$ and $N\_i$ described above. All records are given in increasing order of $T\_i$ .

Output

For each car that left the lot, print one line with two numbers: the car number $N\_i$ and the number of seconds $s\_i$ the car spent in the lot. Print the results in the order in which the cars left the lot.

Constraints

$1 ≤ M, N\_i ≤ 1000$
$1 ≤ T\_i ≤ 1\,000\,000$

Examples1

Example 1

Input

Expected output

123 4000
789 3000
444 11000