#include "wall.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define MP make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define ET cout << "\n"
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
struct node
{
int U,D;
}seg[6000004];
const int INF = 100000;
inline void add(int a,int x)
{
if(!~seg[a].U) seg[a].D=max(seg[a].D,x);
else
if(x>=seg[a].U) seg[a].U=-1,seg[a].D=x;
else seg[a].D=max(seg[a].D,x);
}
inline void remove(int a,int x)
{
if(!~seg[a].U) seg[a].D=min(seg[a].D,x);
else
if(x<=seg[a].D) seg[a].U=-1,seg[a].D=x;
else seg[a].U=min(seg[a].U,x);
}
inline void down(int l,int r,int rt)
{
if(l==r) return;
if(!~seg[rt].U)
seg[rt<<1].U=-1,seg[rt<<1].D=seg[rt].D,seg[rt<<1|1].U=-1,seg[rt<<1|1].D=seg[rt].D;
else
{
if(seg[rt].D!=0) add(rt<<1,seg[rt].D),add(rt<<1|1,seg[rt].D);
if(seg[rt].U!=INF) remove(rt<<1,seg[rt].U),remove(rt<<1|1,seg[rt].U);
}
seg[rt].U=INF,seg[rt].D=0;
}
void modify(int L,int R,int l,int r,int rt,int x,int type)
{
down(l,r,rt);
if(L<=l && R>=r)
{
if(type==1) add(rt,x);
else remove(rt,x);
return;
}
int m=l+r>>1;
if(L<=m) modify(L,R,l,m,rt<<1,x,type);
if(R>m) modify(L,R,m+1,r,rt<<1|1,x,type);
}
void all(int l,int r,int rt,int finalHeight[])
{
down(l,r,rt);
if(l==r) return finalHeight[l]=seg[rt].D,void();
int m=l+r>>1;
all(l,m,rt<<1,finalHeight),all(m+1,r,rt<<1|1,finalHeight);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i=0;i<3*n;++i) seg[i].U=-1,seg[i].D=0;
for(int i=0;i<k;++i) modify(left[i],right[i],0,n-1,1,height[i],op[i]);
all(0,n-1,1,finalHeight);
}
