Insert Interval

Given a list of non-overlapping intervals sorted in ascending order by their start times, and a new interval, insert the new interval into the list so that the intervals remain non-overlapping. If necessary, merge the overlapping intervals.

The merging strategy is as follows: while there are intervals that end before the new interval starts, simply add them to the result. Then, merge all intervals that overlap with the new interval by taking the minimum start and maximum end among them. Finally, add the remaining intervals.

inputFormat

The input is read from standard input (stdin) and consists of multiple lines. The first line contains an integer n, the number of intervals. The next n lines each contain two space-separated integers representing the start and end of each interval. The last line contains two space-separated integers representing the new interval to insert.

outputFormat

Output the merged list of intervals to standard output (stdout). Each interval should be printed on a new line with its start and end values separated by a space.

2
1 3
6 9
2 5

1 5
6 9