#include<vector>
#include<algorithm>
using namespace std;
struct SegTree
{
vector<int> MaxT, MinT;
vector<int> MaxLazy, MinLazy;
int base;
SegTree(int a)
{
base=1;
while(base<a) base<<=1;
MaxT.resize(base*2+2);
MinT.resize(base*2+2);
MaxLazy.resize(base*2+2,-1);
MinLazy.resize(base*2+2,-1);
base--;
}
void propagate(int ns, int nf, int num)
{
int a, b, c;
if(MaxLazy[num]!=-1)
{
c=MaxLazy[num];
if(ns<nf)
{
a=MinT[num*2], b=MaxT[num*2];
if(MinLazy[num*2]!=-1) a=MinLazy[num*2];
if(MaxLazy[num*2]!=-1) b=MaxLazy[num*2];
if(c<a) MaxLazy[num*2]=MinLazy[num*2]=c;
else if(a<=c && c<b) MaxLazy[num*2]=c;
a=MinT[num*2+1], b=MaxT[num*2+1];
if(MinLazy[num*2+1]!=-1) a=MinLazy[num*2+1];
if(MaxLazy[num*2+1]!=-1) b=MaxLazy[num*2+1];
if(c<a) MaxLazy[num*2+1]=MinLazy[num*2+1]=c;
else if(a<=c && c<b) MaxLazy[num*2+1]=c;
}
MaxT[num]=c;
MaxLazy[num]=-1;
}
if(MinLazy[num]!=-1)
{
c=MinLazy[num];
if(ns<nf)
{
a=MinT[num*2], b=MaxT[num*2];
if(MinLazy[num*2]!=-1) a=MinLazy[num*2];
if(MaxLazy[num*2]!=-1) b=MaxLazy[num*2];
if(a<c && c<=b) MinLazy[num*2]=c;
else if(b<c) MinLazy[num*2]=MaxLazy[num*2]=c;
a=MinT[num*2+1], b=MaxT[num*2+1];
if(MinLazy[num*2+1]!=-1) a=MinLazy[num*2+1];
if(MaxLazy[num*2+1]!=-1) b=MaxLazy[num*2+1];
if(a<c && c<=b) MinLazy[num*2+1]=c;
else if(b<c) MinLazy[num*2+1]=MaxLazy[num*2+1]=c;
}
MinT[num]=c;
MinLazy[num]=-1;
}
}
void oper(int op, int v, int st, int fn, int ns=1, int nf=-1, int num=1)
{
if(nf==-1) nf=base+1;
propagate(ns,nf,num);
if(fn<ns || nf<st) return;
if(st<=ns && nf<=fn)
{
int a=MinT[num], b=MaxT[num], c=v;
if(op==1)
{
if(a<c && c<=b) MinLazy[num]=c;
else if(b<c) MinLazy[num]=MaxLazy[num]=c;
}
else if(op==2)
{
if(c<a) MaxLazy[num]=MinLazy[num]=c;
else if(a<=c && c<b) MaxLazy[num]=c;
}
propagate(ns,nf,num);
return;
}
int mid=(ns+nf)>>1;
oper(op,v,st,fn,ns,mid,num*2);
oper(op,v,st,fn,mid+1,nf,num*2+1);
MinT[num]=min(MinT[num*2],MinT[num*2+1]);
MaxT[num]=max(MaxT[num*2],MaxT[num*2+1]);
}
void get_res()
{
int len=base+1, num=1;
while(len!=0)
{
for(int ns=1 ; ns<=base+1 ; ns+=len)
{
propagate(ns,ns+len-1,num);
num++;
}
len>>=1;
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
SegTree T(n);
for(int i=0 ; i<k ; i++)
{
left[i]++, right[i]++;
T.oper(op[i],height[i],left[i],right[i]);
}
T.get_res();
for(int i=0 ; i<n ; i++) finalHeight[i]=T.MinT[T.base+i+1];
}
