#include<bits/stdc++.h>

using namespace std;

struct Interval {
      int start;
      int end;
      Interval() : start(0), end(0) {}
      Interval(int s, int e) : start(s), end(e) {}
  };
 
vector<Interval> insertt(vector<Interval> &intervals, Interval newInterval)
{

int n=intervals.size(),leftfound=0,rightfound=0,count=0;
if(n==0)//for the case when intervals vector is empty
{  intervals.push_back(newInterval);
return intervals;}

int t=0;
if(newInterval.end<newInterval.start)//if(start>end) swap
{
    t=newInterval.start;
    newInterval.start=newInterval.end;
    newInterval.end=t;
}
if(newInterval.start>intervals[n-1].end)//if the newInterval succedes every other
{
    intervals.insert(intervals.end(),newInterval);
    return intervals;
        }
if(newInterval.end<intervals[0].start)//if the newInterval is precedes every other
{
    intervals.insert(intervals.begin(),newInterval);
    return intervals;
      }
      
auto left=intervals.begin(),right=intervals.begin(); //just initialising with something
auto it=intervals.begin() ; // iterator for loops

while((*it).start<newInterval.start&&it!=intervals.end()) //*it is dereferencing the iterator to 
{                                                                //get the element of vector "intervals" at that index
    it++;}
    
it--; // decrementing it to reach the desired interval

if((*it).start<=newInterval.start&&(*it).end>=newInterval.start)
{leftfound=1;left=it;}
else left=it+1;

it=left;

while((*it).end<newInterval.end&&it!=intervals.end())
    it++;

if((*it).start<=newInterval.end&&(*it).end>=newInterval.end)
{ rightfound=1; right=it;
}
else right=it-1;


if(right-left==-1&&leftfound==0&&rightfound==0)// this if will be true in cases like:
   intervals.insert(left,newInterval);          //intervals=[(1,2),(8,10)] and newInterval=(4,6)

else        //in every other case this else will execute
{   
   if(leftfound==0)
   (*left).start=newInterval.start;
   if(rightfound==0)
   (*left).end=newInterval.end;
   else (*left).end=(*right).end;
   //count=right-left;
  
  }
  left=left+1;
  //while(count--)
  //cout<<"current left pe value hai : ("<<left->start<<", "<<left->end<<")"<<endl;
  //cout<<"current right pe value hai : ("<<right->start<<", "<<right->end<<")"<<endl;
  
   intervals.erase(left,right+1);
return intervals;
}

int main()
{
    Interval arr[]={Interval(3,5),Interval(8,10)};
    Interval ni(1,12);
    vector<Interval> intervals(arr,arr+sizeof(arr) / sizeof(arr[0]));
    insertt(intervals,ni);
    /*
    auto it=intervals.begin();
    for(auto it:intervals);
    cout<<it->start<<" "<<it->end;*/
    for (int i = 0; i < intervals.size(); i++) 
    cout<<intervals[i].start<<" "<<intervals[i].end<<" ";
    
    return 0;
}