#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int inf = 1e5;
pii st[1<<22];
int arr[1<<21];
void apply(int i, pii qu){
if(qu.first==-1) return;
if(st[i].first==-1){st[i]=qu; return;}
if(st[i].second <= qu.first)
st[i] = {qu.first,qu.first};
else if(st[i].first >= qu.second)
st[i] = {qu.second,qu.second};
else
st[i] = {max(st[i].first,qu.first),min(st[i].second,qu.second)};
}
void push(int i){
apply(i<<1,st[i]);
apply(i<<1|1,st[i]);
st[i] = {-1,-1};
}
void update(int i, int l, int r, int s, int e, pii qu){
if(r < s || l > e) return;
if(s <= l && r <= e){
apply(i,qu); return;
}
push(i); int m = (l+r)>>1;
update(i<<1,l,m,s,e,qu);
update(i<<1|1,m+1,r,s,e,qu);
}
void build(int i, int l, int r){
if(l==r){arr[l]=st[i].first; return;}
int m = (l+r)>>1; push(i);
build(i<<1,l,m);
build(i<<1|1,m+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
st[1] = {0,0};
for(int i = 0; i < k; i++){
if(op[i]==1) update(1,0,n-1,left[i],right[i],{height[i],inf});
else update(1,0,n-1,left[i],right[i],{0,height[i]});
}
build(1,0,n-1);
for(int i = 0; i < n; i++)
finalHeight[i] = arr[i];
return;
}
