#include <bits/stdc++.h>
#define ll int
using namespace std;
ll s;
struct element
{
ll minn=INT_MIN,maxx=INT_MAX;
};
struct seg_tree
{
vector<element> st,lazy;
void Init(ll n)
{
s=1;
while (s<n)
s <<= 1;
st.resize(2*s+2);
lazy.resize(2*s+2);
}
void Propagate(ll x,ll lx,ll rx)
{
if (lazy[x].minn==INT_MIN && lazy[x].maxx==INT_MAX)
return;
if (lazy[x].minn!=INT_MIN)
{
st[x].minn=max(st[x].minn,lazy[x].minn);
st[x].maxx=max(st[x].maxx,st[x].minn);
if (x<s)
{
lazy[2*x].minn=max(lazy[2*x].minn,lazy[x].minn);
lazy[2*x].maxx=max(lazy[2*x].minn,lazy[2*x].maxx);
lazy[2*x+1].minn=max(lazy[2*x+1].minn,lazy[x].minn);
lazy[2*x+1].maxx=max(lazy[2*x+1].minn,lazy[2*x+1].maxx);
}
}
if (lazy[x].maxx!=INT_MAX)
{
st[x].maxx=min(st[x].maxx,lazy[x].maxx);
st[x].minn=min(st[x].maxx,st[x].minn);
if (x<s)
{
lazy[2*x].maxx=min(lazy[2*x].maxx,lazy[x].maxx);
lazy[2*x].minn=min(lazy[2*x].minn,lazy[2*x].maxx);
lazy[2*x+1].maxx=min(lazy[2*x+1].maxx,lazy[x].maxx);
lazy[2*x+1].minn=min(lazy[2*x+1].minn,lazy[2*x+1].maxx);
}
}
lazy[x]={INT_MIN,INT_MAX};
}
void Add(ll l,ll r,pair<ll,ll> val,ll x,ll lx,ll rx)
{
Propagate(x,lx,rx);
if (lx>r || rx<l)
return;
if (lx>=l && rx<=r)
{
if (val.first==1)
lazy[x]={val.second,INT_MAX};
else
lazy[x]={INT_MIN,val.second};
Propagate(x,lx,rx);
return;
}
ll mid=(lx+rx)/2;
Add(l,r,val,2*x,lx,mid);
Add(l,r,val,2*x+1,mid+1,rx);
}
element Calc(ll pos,ll x,ll lx,ll rx)
{
Propagate(x,lx,rx);
if (lx==rx)
return st[x];
ll mid=(lx+rx)/2;
if (pos<=mid)
return Calc(pos,2*x,lx,mid);
return Calc(pos,2*x+1,mid+1,rx);
}
};
seg_tree S;
void buildWall(ll n,ll k,ll op[],ll left[],ll right[],ll height[],ll finalHeight[])
{
S.Init(n);
for (ll i=0;i<k;i++)
S.Add(left[i]+1,right[i]+1,{op[i],height[i]},1,1,s);
for (ll i=0;i<n;i++)
finalHeight[i]=max(0,S.Calc(i+1,1,1,s).minn);
}
