Merge booking times

Problem

A room has booking requests as start and end times. Merge all bookings that overlap or touch (a booking that starts exactly when the previous one ends). Print the merged bookings in order of start time, one per line as start end. The starter holds a program with a bug. Find it and fix it.

Input, output and limits

Input: Line 1: n. Next n lines: two integers start and end, with start ≤ end.
Output: The merged bookings, one start end per line, ordered by start.
Constraints: 1 ≤ n ≤ 1000
0 ≤ start ≤ end ≤ 100000
The requests are in any order

Examples

Example

Input

Output

1 6
8 10

The first two overlap and join into 1 6.

Hints

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

Hint 1

Sort the bookings by start time first.

Hint 2

A booking joins the last merged one when its start is at most the last end.

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

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Testing Your Solutions problems

Problem

Input, output and limits

Examples

Hints

More Testing Your Solutions problems