#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,3},{6,9}};
	pair<int,int> p1={2,5};
		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+IHYxPXt7MSwzfSx7Niw5fX07CglwYWlyPGludCxpbnQ+IHAxPXsyLDV9OwoJCXZlY3RvcjxwYWlyPGludCxpbnQ+PiBhbnM9aGVscGVyKHYxLHAxKTsKCQlmb3IoYXV0byB0OmFucykKCQl7CgkJCWNvdXQ8PHQuZmlyc3Q8PCIgIjw8dC5zZWNvbmQ8PGVuZGw7CgkJfQoJcmV0dXJuIDA7Cn0KCgoKLy8gWW91IGFyZSBnaXZlbiBhbiBhcnJheSBvZiBub24tb3ZlcmxhcHBpbmcgaW50ZXJ2YWxzIGludGVydmFscyB3aGVyZSBpbnRlcnZhbHNbaV0gPSBbc3RhcnRpLCBlbmRpXSByZXByZXNlbnQgdGhlIHN0YXJ0IGFuZCB0aGUgZW5kIG9mIHRoZSBpdGggaW50ZXJ2YWwgYW5kIGludGVydmFscyBpcyBzb3J0ZWQgaW4gYXNjZW5kaW5nIG9yZGVyIGJ5IHN0YXJ0aS4gWW91IGFyZSBhbHNvIGdpdmVuIGFuIGludGVydmFsIG5ld0ludGVydmFsID0gW3N0YXJ0LCBlbmRdIHRoYXQgcmVwcmVzZW50cyB0aGUgc3RhcnQgYW5kIGVuZCBvZiBhbm90aGVyIGludGVydmFsLgovLyBJbnNlcnQgbmV3SW50ZXJ2YWwgaW50byBpbnRlcnZhbHMgc3VjaCB0aGF0IGludGVydmFscyBpcyBzdGlsbCBzb3J0ZWQgaW4gYXNjZW5kaW5nIG9yZGVyIGJ5IHN0YXJ0aSBhbmQgaW50ZXJ2YWxzIHN0aWxsIGRvZXMgbm90IGhhdmUgYW55IG92ZXJsYXBwaW5nIGludGVydmFscyAobWVyZ2Ugb3ZlcmxhcHBpbmcgaW50ZXJ2YWxzIGlmIG5lY2Vzc2FyeSkuCi8vIFJldHVybiBpbnRlcnZhbHMgYWZ0ZXIgdGhlIGluc2VydGlvbi4KLy8gTm90ZSB0aGF0IHlvdSBkb24ndCBuZWVkIHRvIG1vZGlmeSBpbnRlcnZhbHMgaW4tcGxhY2UuIFlvdSBjYW4gbWFrZSBhIG5ldyBhcnJheSBhbmQgcmV0dXJuIGl0LgogCi8vIEV4YW1wbGUgMToKLy8gSW5wdXQ6IGludGVydmFscyA9IFtbMSwzXSxbNiw5XV0sIG5ld0ludGVydmFsID0gWzIsNV0KLy8gT3V0cHV0OiBbWzEsNV0sWzYsOV1dCi8vIEV4YW1wbGUgMjoKLy8gSW5wdXQ6IGludGVydmFscyA9IFtbMSwyXSxbMyw1XSxbNiw3XSxbOCwxMF0sWzEyLDE2XV0sIG5ld0ludGVydmFsID0gWzQsOF0KLy8gT3V0cHV0OiBbWzEsMl0sWzMsMTBdLFsxMiwxNl1dCi8vIEV4cGxhbmF0aW9uOiBCZWNhdXNlIHRoZSBuZXcgaW50ZXJ2YWwgWzQsOF0gb3ZlcmxhcHMgd2l0aCBbMyw1XSxbNiw3XSxbOCwxMF0u

MTAKYWJhCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtz

10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks