You are given an array of non-overlapping intervals sorted by start time, and a new interval. Insert the new interval, merging if necessary.

Example 1:

Input:
3
1 3
6 9
2 5
Output: 1 5
        6 9

Input format: Line 1 = n (existing intervals). Next n lines = start end. Last line = new interval start end.

Output format: One interval per line.