Insert Interval

Problem Statement : Given a sorted list of non overlapping intervals and a new interval, insert the new interval into the list while maintaining the sorted order and merging any overlapping intervals if necessary. The intervals are initially sorted based on their start times. Input Specification : The first line contains an integer N, the number of existing intervals. Subsequent N lines contain two space separated integers each, representing the start and end of an interval. The last line contains two space separated integers, representing the new interval to be inserted. Output Specification : Print the modified list of intervals after insertion and merging. Each interval should be on a new line as two space separated integers (start end). Constraints : 0 <= N <= 10^4 10^5 <= interval start <= interval end <= 10^5 Intervals are initially sorted by start time New interval may overlap with existing ones or be completely outside all intervals Sample Input 1 : Sample Output 1 : Sample Input 2 : Sample Output 2 : Difficulty Level : Medium