#include <iostream>
#include<stdio.h>
#include<memory.h>
#include<limits.h>
#include<string.h>
#include<vector> 
using namespace std;
 
char str[100005];
int hashmap[300];
static bool cmp(pair<int,int> p1,pair<int,int> p2)
{
	if(p1.first<p2.first)
	return true;
	return p1.second<p2.second;
}
vector<pair<int,int>> helper(vector<pair<int,int>> intervalList,pair<int,int> newInterval)
{
	// sort(intervalList.begin(),intervalList.end(),cmp);
	int n=intervalList.size();
	vector<pair<int,int>> ans;
	int start=newInterval.first;
	int end=newInterval.second;
 
	for(int i=0;i<n;i++)
	{
		if(start>intervalList[i].second)
		{
			ans.push_back(intervalList[i]);
		}else if(end<intervalList[i].first)
		{
		ans.push_back({start,end});	
		ans.push_back(intervalList[i]);
		}
		else
		{
			start=min(start,intervalList[i].first);
			end=max(end,intervalList[i].second);
			if(i==n-1)
			{
					ans.push_back({start,end});	
			}
		}
	}
	return ans;
}
 
int main() 
{
	vector<pair<int,int>> v1={{1,2},{3,5},{6,7},{8,10},{12,16}};
	pair<int,int> p1={4,10};
		vector<pair<int,int>> ans=helper(v1,p1);
		for(auto t:ans)
		{
			cout<<t.first<<" "<<t.second<<endl;
		}
	return 0;
}
 
 
 
// You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
// Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
// Return intervals after the insertion.
// Note that you don't need to modify intervals in-place. You can make a new array and return it.
 
// Example 1:
// Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
// Output: [[1,5],[6,9]]
// Example 2:
// Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
// Output: [[1,2],[3,10],[12,16]]
// Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZTxzdGRpby5oPgojaW5jbHVkZTxtZW1vcnkuaD4KI2luY2x1ZGU8bGltaXRzLmg+CiNpbmNsdWRlPHN0cmluZy5oPgojaW5jbHVkZTx2ZWN0b3I+IAp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCmNoYXIgc3RyWzEwMDAwNV07CmludCBoYXNobWFwWzMwMF07CnN0YXRpYyBib29sIGNtcChwYWlyPGludCxpbnQ+IHAxLHBhaXI8aW50LGludD4gcDIpCnsKCWlmKHAxLmZpcnN0PHAyLmZpcnN0KQoJcmV0dXJuIHRydWU7CglyZXR1cm4gcDEuc2Vjb25kPHAyLnNlY29uZDsKfQp2ZWN0b3I8cGFpcjxpbnQsaW50Pj4gaGVscGVyKHZlY3RvcjxwYWlyPGludCxpbnQ+PiBpbnRlcnZhbExpc3QscGFpcjxpbnQsaW50PiBuZXdJbnRlcnZhbCkKewoJLy8gc29ydChpbnRlcnZhbExpc3QuYmVnaW4oKSxpbnRlcnZhbExpc3QuZW5kKCksY21wKTsKCWludCBuPWludGVydmFsTGlzdC5zaXplKCk7Cgl2ZWN0b3I8cGFpcjxpbnQsaW50Pj4gYW5zOwoJaW50IHN0YXJ0PW5ld0ludGVydmFsLmZpcnN0OwoJaW50IGVuZD1uZXdJbnRlcnZhbC5zZWNvbmQ7CgoJZm9yKGludCBpPTA7aTxuO2krKykKCXsKCQlpZihzdGFydD5pbnRlcnZhbExpc3RbaV0uc2Vjb25kKQoJCXsKCQkJYW5zLnB1c2hfYmFjayhpbnRlcnZhbExpc3RbaV0pOwoJCX1lbHNlIGlmKGVuZDxpbnRlcnZhbExpc3RbaV0uZmlyc3QpCgkJewoJCWFucy5wdXNoX2JhY2soe3N0YXJ0LGVuZH0pOwkKCQlhbnMucHVzaF9iYWNrKGludGVydmFsTGlzdFtpXSk7CgkJfQoJCWVsc2UKCQl7CgkJCXN0YXJ0PW1pbihzdGFydCxpbnRlcnZhbExpc3RbaV0uZmlyc3QpOwoJCQllbmQ9bWF4KGVuZCxpbnRlcnZhbExpc3RbaV0uc2Vjb25kKTsKCQkJaWYoaT09bi0xKQoJCQl7CgkJCQkJYW5zLnB1c2hfYmFjayh7c3RhcnQsZW5kfSk7CQoJCQl9CgkJfQoJfQoJcmV0dXJuIGFuczsKfQoKaW50IG1haW4oKSAKewoJdmVjdG9yPHBhaXI8aW50LGludD4+IHYxPXt7MSwyfSx7Myw1fSx7Niw3fSx7OCwxMH0sezEyLDE2fX07CglwYWlyPGludCxpbnQ+IHAxPXs0LDEwfTsKCQl2ZWN0b3I8cGFpcjxpbnQsaW50Pj4gYW5zPWhlbHBlcih2MSxwMSk7CgkJZm9yKGF1dG8gdDphbnMpCgkJewoJCQljb3V0PDx0LmZpcnN0PDwiICI8PHQuc2Vjb25kPDxlbmRsOwoJCX0KCXJldHVybiAwOwp9CgoKCi8vIFlvdSBhcmUgZ2l2ZW4gYW4gYXJyYXkgb2Ygbm9uLW92ZXJsYXBwaW5nIGludGVydmFscyBpbnRlcnZhbHMgd2hlcmUgaW50ZXJ2YWxzW2ldID0gW3N0YXJ0aSwgZW5kaV0gcmVwcmVzZW50IHRoZSBzdGFydCBhbmQgdGhlIGVuZCBvZiB0aGUgaXRoIGludGVydmFsIGFuZCBpbnRlcnZhbHMgaXMgc29ydGVkIGluIGFzY2VuZGluZyBvcmRlciBieSBzdGFydGkuIFlvdSBhcmUgYWxzbyBnaXZlbiBhbiBpbnRlcnZhbCBuZXdJbnRlcnZhbCA9IFtzdGFydCwgZW5kXSB0aGF0IHJlcHJlc2VudHMgdGhlIHN0YXJ0IGFuZCBlbmQgb2YgYW5vdGhlciBpbnRlcnZhbC4KLy8gSW5zZXJ0IG5ld0ludGVydmFsIGludG8gaW50ZXJ2YWxzIHN1Y2ggdGhhdCBpbnRlcnZhbHMgaXMgc3RpbGwgc29ydGVkIGluIGFzY2VuZGluZyBvcmRlciBieSBzdGFydGkgYW5kIGludGVydmFscyBzdGlsbCBkb2VzIG5vdCBoYXZlIGFueSBvdmVybGFwcGluZyBpbnRlcnZhbHMgKG1lcmdlIG92ZXJsYXBwaW5nIGludGVydmFscyBpZiBuZWNlc3NhcnkpLgovLyBSZXR1cm4gaW50ZXJ2YWxzIGFmdGVyIHRoZSBpbnNlcnRpb24uCi8vIE5vdGUgdGhhdCB5b3UgZG9uJ3QgbmVlZCB0byBtb2RpZnkgaW50ZXJ2YWxzIGluLXBsYWNlLiBZb3UgY2FuIG1ha2UgYSBuZXcgYXJyYXkgYW5kIHJldHVybiBpdC4KIAovLyBFeGFtcGxlIDE6Ci8vIElucHV0OiBpbnRlcnZhbHMgPSBbWzEsM10sWzYsOV1dLCBuZXdJbnRlcnZhbCA9IFsyLDVdCi8vIE91dHB1dDogW1sxLDVdLFs2LDldXQovLyBFeGFtcGxlIDI6Ci8vIElucHV0OiBpbnRlcnZhbHMgPSBbWzEsMl0sWzMsNV0sWzYsN10sWzgsMTBdLFsxMiwxNl1dLCBuZXdJbnRlcnZhbCA9IFs0LDhdCi8vIE91dHB1dDogW1sxLDJdLFszLDEwXSxbMTIsMTZdXQovLyBFeHBsYW5hdGlvbjogQmVjYXVzZSB0aGUgbmV3IGludGVydmFsIFs0LDhdIG92ZXJsYXBzIHdpdGggWzMsNV0sWzYsN10sWzgsMTBdLg==

MTAKYWJhCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtz

10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks