#include <bits/stdc++.h>
#include "wall.h"
#define inf 1000000007
#define mod 1000000007
#define lson (p<<1)
#define rson (p<<1|1)
#define rnd() rand_num()
#define bigrnd() dis(rand_num)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
//#define int long long
using namespace std;
unsigned sed=std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(sed);
uniform_int_distribution<long long> dis(0,inf);
template <typename T> void read(T &x){
x=0;char ch=getchar();int fh=1;
while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
x*=fh;
}
template <typename T> void write(T x) {
if (x<0) x=-x,putchar('-');
if (x>9) write(x/10);
putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
int mx[8000005],mn[8000005],tag[8000005];
void pushup(int p)
{
mx[p]=max(mx[lson],mx[rson]);
mn[p]=min(mn[lson],mn[rson]);
}
void build(int p,int l,int r)
{
if(l==r)
{
mx[p]=mn[p]=0;
tag[p]=-1;
return;
}
int mid=l+r>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(p);
}
void pushdown(int p)
{
if(tag[p]!=-1)
{
mx[lson]=mn[lson]=tag[lson]=mx[rson]=mn[rson]=tag[rson]=tag[p];
tag[p]=-1;
}
}
void add(int p,int l,int r,int x,int y,int k)
{
if(mn[p]>=k) return;
if(x<=l&&r<=y)
{
if(mx[p]<=k)
{
mx[p]=mn[p]=tag[p]=k;
return;
}
}
pushdown(p);
int mid=l+r>>1;
if(x<=mid) add(lson,l,mid,x,y,k);
if(mid+1<=y) add(rson,mid+1,r,x,y,k);
pushup(p);
}
void remove(int p,int l,int r,int x,int y,int k)
{
if(mx[p]<=k) return;
if(x<=l&&r<=y)
{
if(mn[p]>=k)
{
mx[p]=mn[p]=tag[p]=k;
return;
}
}
pushdown(p);
int mid=l+r>>1;
if(x<=mid) remove(lson,l,mid,x,y,k);
if(mid+1<=y) remove(rson,mid+1,r,x,y,k);
pushup(p);
}
int query(int p,int l,int r,int x)
{
if(l==r)
return mx[p];
pushdown(p);
int mid=l+r>>1;
if(x<=mid) return query(lson,l,mid,x);
else return query(rson,mid+1,r,x);
}
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)
{
if(op[i]==1)
add(1,1,n,left[i]+1,right[i]+1,height[i]);
else
remove(1,1,n,left[i]+1,right[i]+1,height[i]);
}
for(int i=0;i<n;++i)
finalHeight[i]=query(1,1,n,i+1);
}
