588. Insert Interval

0

Medium

Given a sorted array of non-overlapping intervals, intervals, and a new interval, newInterval, insert newInterval into intervals while maintaining the sorted order and ensuring that there are no overlapping intervals. If necessary, merge any overlapping intervals. Finally, print the intervals in sorted order based on the first value.

Input Format

The input consists of the following:
- The number of rows in the 2D array
- The number of columns in the 2D array
- The 2D array representing the intervals
- The size of the newInterval array
- The intervals of the newInterval array

Output Format

Print the intervals in the form of a 2D array

Example

Input

2
2
1 3
6 9
2
2 5

Output

1 5
6 9

Constraints

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 10^5

Loading...

View Submissions

Console