#include<algorithm>
using namespace std;
int lo[1<<22],hi[1<<22],base=1<<21;
void init()
{
int sz=1<<22;
for(int i=1;i<sz;i++)
lo[i]=0, hi[i]=100000;
}
void down(int now)
{
if(now>=base) return;
hi[now*2]=min(max(hi[now*2],lo[now]),hi[now]);
lo[now*2]=max(min(lo[now*2],hi[now]),lo[now]);
hi[now*2+1]=min(max(hi[now*2+1],lo[now]),hi[now]);
lo[now*2+1]=max(min(lo[now*2+1],hi[now]),lo[now]);
lo[now]=0, hi[now]=100000;
}
void update(int l,int r,int type,int value,int now,int now_l,int now_r)
{
down(now);
if(now_r<l || now_l>r) return;
else if(l<=now_l && now_r<=r)
{
if(type==0)
{
lo[now]=max(lo[now],value);
hi[now]=max(hi[now],value);
}
else
{
hi[now]=min(hi[now],value);
lo[now]=min(lo[now],value);
}
down(now);
}
else
{
int mid=(now_l+now_r)/2;
update(l,r,type,value,now*2,now_l,mid);
update(l,r,type,value,now*2+1,mid+1,now_r);
}
}
void make_res(int now,int now_l,int now_r)
{
down(now);
if(now_l==now_r) return;
int mid=(now_l+now_r)/2;
make_res(now*2,now_l,mid);
make_res(now*2+1,mid+1,now_r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
init();
for(int i=0;i<k;i++)
update(left[i]+1,right[i]+1,op[i]-1,height[i],1,1,base);
make_res(1,1,base);
for(int i=0;i<n;i++)
finalHeight[i]=lo[i+base];
}
