Merge booking intervals

Problem

The computer lab keeps a booking register. Booking i holds the lab from minute start to minute end, and both of these minutes are part of the booking. The lab assistant wants a short list of the periods when the lab is busy.

Two bookings join into one period when they overlap or touch: 1 3 and 3 5 become 1 5. Bookings with a free minute between them stay apart: 1 5 and 6 8 are two periods. Print the busy periods after joining everything that can be joined, sorted by start.

Input, output and limits

Input: The first line has one integer n. Each of the next n lines has two integers start end for one booking.
Output: One line start end for each busy period, sorted from earliest to latest.
Constraints: 1 ≤ n ≤ 10^5
0 ≤ start ≤ end ≤ 10^9

Examples

Example

Input

Output

1 6
8 10
15 18

1 3 and 2 6 overlap, so they join into 1 6. The other two bookings stay as they are.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Bookings that join are easy to find when they sit next to each other. What order helps?

Hint 2

Sort the bookings by start. Keep one current period, starting with the first booking.

Hint 3

If the next booking starts at or before the end of the current period, stretch the end. Otherwise the current period is finished.

Hint 4

When stretching, keep the larger of the two ends, because a booking can sit fully inside the current period. Do not forget to print the last period.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Greedy & Interval problems

Problem

Input, output and limits

Examples

Hints

More Greedy & Interval problems