IntervalsArray
You are given a list of non-overlapping intervals sorted by start time, and one new interval. Insert the new interval into the list, merging any intervals it overlaps, and keep the list sorted. Touching intervals count as overlapping.
Input
Line 1: n. Next n lines: the sorted, non-overlapping intervals. Last line: the start and end of the new interval.
Output
Print the resulting intervals one per line as 'start end'.
Constraints
0 <= n <= 10^4, but n >= 1 in these tests 0 <= start <= end <= 10^5
Example 1
Input
2 1 3 6 9 2 5
Output
1 5 6 9
[2,5] overlaps [1,3], producing [1,5].
Example 2
Input
5 1 2 3 5 6 7 8 10 12 16 4 8
Output
1 2 3 10 12 16
[4,8] swallows [3,5], [6,7] and [8,10], producing [3,10].