Merge Overlapping Intervals

Northgate Studios rents out one recording booth, and bookings arrive from several agents who cannot see each other's diaries, so the day's list comes in unordered and full of overlaps -- two agents can both promise the booth from 2 until 6. The front desk needs the day boiled down to the stretches when the booth is genuinely busy, so the rest can be sold as free time.

Task: Print the busy stretches, with every overlap collapsed into one, in increasing order of start time.

Input

The first line holds an integer n, the number of bookings, with 1 <= n <= 1000. Each of the next n lines holds two integers start and end separated by a single space, with 0 <= start <= end. The bookings arrive in no particular order.

Output

One line per busy stretch, written as start end separated by a single space, ordered by start. Bookings that only touch -- one ends exactly where the next begins -- count as a single stretch.

Example:

Input:
3
1 3
2 6
8 10

Output:
1 6
8 10