#include<bits/stdc++.h>
using namespace std;
#define N 2000005
struct A{
int mi,ma,exact;
};
A t[4*N];
int ll,rr,ma,mi;
void op(A &t,A add){
auto [mi,ma,exact]=add;
if(exact!=-1)t=add;
else if(t.mi!=-1){
if(t.exact==-1){
t.ma=min(t.ma,ma);
t.mi=max(t.mi,mi);
if(t.mi>t.ma){
if(t.mi==mi)t.exact=mi;
else t.exact=ma;
}
}
else{
if(t.exact<mi)t.exact=mi;
else if(t.exact>ma)t.exact=ma;
}
}
else t=add;
}
void push(int x){
if(t[x].mi!=-1){
int xl=x*2,xr=xl+1,mi=t[x].mi,ma=t[x].ma;
op(t[xl],t[x]);
op(t[xr],t[x]);
t[x].mi=-1;
}
}
void cre(int x,int l,int r){
if(l==r)return ;
t[x]={-1,-1,-1};
int mid=(l+r)/2;
cre(x*2,l,mid);
cre(x*2+1,mid+1,r);
}
void update(int x,int l,int r){
if(r<ll||rr<l)return ;
if(ll<=l&&r<=rr){
op(t[x],{mi,ma,-1});
return ;
}
push(x);
int mid=(l+r)/2;
update(x*2,l,mid);
update(x*2+1,mid+1,r);
}
void sol(int x,int l,int r,int *ans){
if(l==r){ans[l-1]=t[x].exact;return ;}
push(x);
int mid=(l+r)/2;
sol(x*2,l,mid,ans);
sol(x*2+1,mid+1,r,ans);
}
void buildWall(int n, int k, int *op, int *left, int *right, int *height, int *finalHeight){
int i,h;
cre(1,1,n);
for(i=0;i<k;i++){
ll=left[i]+1;
rr=right[i]+1;
h=height[i];
if(op[i]==1)mi=h,ma=100000;
else mi=0,ma=h;
update(1,1,n);
}
sol(1,1,n,finalHeight);
}
