#include<bits/stdc++.h>
using namespace std;
#define N 2000005
struct A{
int mi,ma,exact;
};
A t[4*N],lazy[4*N];
int ll,rr,ma,mi;
void push(int x){
if(lazy[x].mi!=-1){
int xl=x*2,xr=xl+1,mi=lazy[x].mi,ma=lazy[x].ma;
if(lazy[x].exact!=-1)lazy[xl]=lazy[xr]=lazy[x];
else{
if(lazy[xl].mi==-1)lazy[xl]=lazy[x];
else if(lazy[xl].exact==-1){
lazy[xl].ma=min(lazy[xl].ma,ma);
lazy[xl].mi=max(lazy[xl].mi,mi);
if(lazy[xl].mi>lazy[xl].ma){
if(mi==0)lazy[xl].exact=ma;
else lazy[xl].exact=mi;
}
}
else{
if(lazy[xl].exact<mi)lazy[xl].exact=mi;
else if(lazy[xl].exact>ma)lazy[xl].exact=ma;
}
if(lazy[xr].mi==-1)lazy[xr]=lazy[x];
else if(lazy[xr].exact==-1){
lazy[xr].ma=min(lazy[xr].ma,ma);
lazy[xr].mi=max(lazy[xr].mi,mi);
if(lazy[xr].mi>lazy[xr].ma){
if(mi==0)lazy[xr].exact=ma;
else lazy[xr].exact=mi;
}
}
else{
if(lazy[xr].exact<mi)lazy[xr].exact=mi;
else if(lazy[xr].exact>ma)lazy[xr].exact=ma;
}
}
if(lazy[x].exact!=-1)t[xl]=lazy[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(mi==0)t[xl].exact=ma;
else t[xl].exact=mi;
}
}
else{
if(t[xl].exact<mi)t[xl].exact=mi;
else if(t[xl].exact>ma)t[xl].exact=ma;
}
if(lazy[x].exact!=-1)t[xr]=lazy[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(mi==0)t[xr].exact=ma;
else t[xr].exact=mi;
}
}
else{
if(t[xr].exact<mi)t[xr].exact=mi;
else if(t[xr].exact>ma)t[xr].exact=ma;
}
lazy[x].mi=-1;
}
}
void cre(int x,int l,int r){
if(l==r)return ;
t[x]={0,10000,-1};
lazy[x].mi=-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].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(mi==0)t[x].exact=ma;
else t[x].exact=mi;
}
}
else{
if(t[x].exact<mi)t[x].exact=mi;
else if(t[x].exact>ma)t[x].exact=ma;
}
if(lazy[x].mi!=-1){
if(lazy[x].exact==-1){
lazy[x].ma=min(lazy[x].ma,ma);
lazy[x].mi=max(lazy[x].mi,mi);
if(lazy[x].mi>lazy[x].ma){
if(mi==0)lazy[x].exact=ma;
else lazy[x].exact=mi;
}
}
else{
if(lazy[x].exact<mi)lazy[x].exact=mi;
else if(lazy[x].exact>ma)lazy[x].exact=ma;
}
}
else lazy[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);
}
