#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 push(int x){
if(t[x].mi!=-1){
int xl=x*2,xr=xl+1,mi=t[x].mi,ma=t[x].ma;
if(t[x].exact!=-1)t[xl]=t[xr]=t[x];
else{
if(t[xl].mi==-1)t[xl]=t[x];
else if(t[xl].exact==-1){
t[xl].ma=min(t[xl].ma,ma);
t[xl].mi=max(t[xl].mi,mi);
if(t[xl].mi>t[xl].ma){
if(t[xl].mi==mi)t[xl].exact=mi;
else t[xl].exact=ma;
}
}
else{
if(t[xl].exact<mi)t[xl].exact=mi;
else if(t[xl].exact>ma)t[xl].exact=ma;
}
if(t[xr].mi==-1)t[xr]=t[x];
else if(t[xr].exact==-1){
t[xr].ma=min(t[xr].ma,ma);
t[xr].mi=max(t[xr].mi,mi);
if(t[xr].mi>t[xr].ma){
if(t[xr].mi==mi)t[xr].exact=mi;
else t[xr].exact=ma;
}
}
else{
if(t[xr].exact<mi)t[xr].exact=mi;
else if(t[xr].exact>ma)t[xr].exact=ma;
}
}
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){
if(t[x].mi!=-1){
if(t[x].exact==-1){
t[x].ma=min(t[x].ma,ma);
t[x].mi=max(t[x].mi,mi);
if(t[x].mi>t[x].ma){
if(t[x].mi==mi)t[x].exact=mi;
else t[x].exact=ma;
}
}
else{
if(t[x].exact<mi)t[x].exact=mi;
else if(t[x].exact>ma)t[x].exact=ma;
}
}
else 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);
}
