#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define piii pair<int,pii>
#define F first
#define S second.first
#define T second.second
const int N=2e6+10,off=(1<<21);
const piii stan={-1,{0,1e9+10}};
piii tour[4*off+5];
pii ans[N];
piii Merge(piii m1,piii m2){
if(m1.F>m2.F)swap(m1,m2);
if(m2.T<m1.S)return {m2.F,{m2.T,m2.T}};
if(m2.S>m1.T)return {m2.F,{m2.S,m2.S}};
return {m2.F,{max(m1.S,m2.S),min(m1.T,m2.T)}};
}
void update(int x,int y,int l,int r,int node,piii val){
if(r<x or l>y)return;
if(x<=l and r<=y){
tour[node]=Merge(tour[node],val);
return;
}
tour[node*2]=Merge(tour[node*2],tour[node]);
tour[node*2+1]=Merge(tour[node*2+1],tour[node]);
update(x,y,l,(l+r)/2,node*2,val);
update(x,y,(l+r)/2+1,r,node*2+1,val);
return;
}
void query(int x,int y,int l,int r,int node){
if(l>y)return;
if(l==r){
ans[l]={tour[node].S,tour[node].T};
return;
}
tour[node*2]=Merge(tour[node*2],tour[node]);
tour[node*2+1]=Merge(tour[node*2+1],tour[node]);
tour[node]=stan;
query(x,y,l,(l+r)/2,node*2);
query(x,y,(l+r)/2+1,r,node*2+1);
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<4*off+5;i++)tour[i]=stan;
for(int i=0;i<k;i++){
if(op[i]==1)update(left[i],right[i],0,off-1,1,{i+1,{height[i],1e9+10}});
else update(left[i],right[i],0,off-1,1,{i+1,{0,height[i]}});
}
query(0,n-1,0,off-1,1);
for(int i=0;i<n;i++){
finalHeight[i]=max(finalHeight[i],ans[i].first);
finalHeight[i]=min(finalHeight[i],ans[i].second);
}
return;
}
