#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int STmn[4*N],STmx[4*N],lazymin[4*N],lazymax[4*N],res[N];
void build(int id,int l,int r)
{
lazymin[id]=1e9;
lazymax[id]=0;
if(l==r) return ;
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void dolazy(int id,int l,int r)
{
STmn[id]=min(STmn[id],lazymin[id]);
STmn[id]=max(STmn[id],lazymax[id]);
STmx[id]=min(STmx[id],lazymin[id]);
STmx[id]=max(STmx[id],lazymax[id]);
if(l!=r)
{
lazymin[id*2]=min(lazymin[id*2],lazymin[id]);
lazymin[id*2+1]=min(lazymin[id*2+1],lazymin[id]);
lazymin[id*2]=max(lazymin[id*2],lazymax[id]);
lazymin[id*2+1]=max(lazymin[id*2+1],lazymax[id]);
lazymax[id*2+1]=min(lazymax[id*2+1],lazymin[id]);
lazymax[id*2]=min(lazymax[id*2],lazymin[id]);
lazymax[id*2+1]=max(lazymax[id*2+1],lazymax[id]);
lazymax[id*2]=max(lazymax[id*2],lazymax[id]);
}
lazymax[id]=0;
lazymin[id]=1e9;
}
void update(int id,int l,int r,int L,int R,int type,int val)
{
dolazy(id,l,r);
if(R<l||r<L) return;
if(L<=l&&r<=R)
{
if(type==1)
{
lazymin[id]=max(lazymin[id],val);
lazymax[id]=max(lazymax[id],val);
}
else if(type==2)
{
lazymin[id]=min(lazymin[id],val);
lazymax[id]=min(lazymax[id],val);
}
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,L,R,type,val);
update(id*2+1,mid+1,r,L,R,type,val);
STmx[id]=max(STmx[id*2],STmx[id*2+1]);
STmn[id]=min(STmn[id*2],STmn[id*2+1]);
}
void comp(int id, int l, int r)
{
dolazy(id,l,r);
if(l==r)
{
res[l]=STmn[id];
return;
}
int mid=(l+r)/2;
comp(id*2,l,mid);
comp(id*2+1,mid+1,r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
build(1,1,n);
for(int i=0;i<k;i++)
{
left[i]++;
right[i]++;
update(1,1,n,left[i],right[i],op[i],height[i]);
}
comp(1,1,n);
for(int i=0;i<n;i++) finalHeight[i]=res[i-1];
}
