Insert Interval

You are given sorted, non-overlapping intervals and one new interval. Insert the new interval and merge overlaps. Input format: - First line: n - Next n lines: start end - Last line: newStart newEnd Print the merged intervals in sorted order, one interval per line as `start end`.

0 <= n <= 10^4
-10^9 <= start <= end <= 10^9

2
1 3
6 9
2 5

1 5
6 9

5
1 2
3 5
6 7
8 10
12 16
4 8

1 2
3 10
12 16