#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int lim=2e6+100;
struct{
struct{
int rem=0,add=0;
int last=0;
}tree[4*lim];
int ans[lim]{};
int n;
void push(int node,int l,int r){
if(l==r){
if(tree[node].last){
ans[l]=max(ans[l],tree[node].add);
ans[l]=min(ans[l],tree[node].rem);
}else{
ans[l]=min(ans[l],tree[node].rem);
ans[l]=max(ans[l],tree[node].add);
}
}else{
int child=node<<1;
if(tree[node].last){
tree[child].rem=max(tree[child].rem,tree[node].add);
tree[child].add=max(tree[child].add,tree[node].add);
tree[child].rem=min(tree[child].rem,tree[node].rem);
tree[child].add=min(tree[child].add,tree[node].rem);
}else{
tree[child].rem=min(tree[child].rem,tree[node].rem);
tree[child].add=min(tree[child].add,tree[node].rem);
tree[child].rem=max(tree[child].rem,tree[node].add);
tree[child].add=max(tree[child].add,tree[node].add);
}
tree[child].last=tree[node].last;
child++;
if(tree[node].last){
tree[child].rem=max(tree[child].rem,tree[node].add);
tree[child].add=max(tree[child].add,tree[node].add);
tree[child].rem=min(tree[child].rem,tree[node].rem);
tree[child].add=min(tree[child].add,tree[node].rem);
}else{
tree[child].rem=min(tree[child].rem,tree[node].rem);
tree[child].add=min(tree[child].add,tree[node].rem);
tree[child].rem=max(tree[child].rem,tree[node].add);
tree[child].add=max(tree[child].add,tree[node].add);
}
tree[child].last=tree[node].last;
}
tree[node].rem=200000;
tree[node].add=0;
}
int L,R;
int TY,VAL;
void update(int l,int r,int node){
if(r<L||R<l)return;
push(node,l,r);
if(L<=l&&r<=R){
if(TY){
tree[node].add=VAL;
}else{
tree[node].rem=VAL;
}
tree[node].last=TY;
return;
}
int mid=(l+r)>>1,child=node<<1;
update(l,mid,child),update(mid+1,r,child|1);
}
void update(int l,int r,int val,int ty){
L=l,R=r,VAL=val,TY=ty;
update(0,n-1,1);
}
void walk(int l,int r,int node){
push(node,l,r);
if(l==r)return;
int mid=(l+r)>>1,child=node<<1;
walk(l,mid,child),walk(mid+1,r,child|1);
}
}st;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
st.n=n;
for(int i=0;i<k;i++){
st.update(left[i],right[i],height[i],op[i]&1);
}
st.walk(0,n-1,1);
for(int i=0;i<n;i++){
finalHeight[i]=st.ans[i];
}
}
