#include <bits/stdc++.h>
using namespace std;
int seg[6000001];
void build(int p,int l,int r){
if(l==r){
seg[p] = 0;
return ;
}
int md = (l+r)/2;
build(p*2,l,md);build(p*2+1,md+1,r);
}
int li[6000001],ri[6000001];
void prop(int p,int l,int r){
if(li[p]==-1)return ;
//cout<<l<<" "<<r<<" "<<li[p]<<" "<<ri[p]<<endl;
if(l==r){
if(seg[p]<li[p]){
seg[p] = li[p];
}if(seg[p]>ri[p]){
seg[p] = ri[p];
}
}
if(l!=r){
if(li[p*2]==-1){
li[p*2] = li[p];
ri[p*2] = ri[p];
}else{
if(ri[p*2]<li[p]){
li[p*2] = li[p];
ri[p*2] = li[p];
}else if(ri[p]<li[p*2]){
li[p*2] = ri[p];
ri[p*2] = ri[p];
}else{
li[p*2] = max(li[p*2],li[p]);
ri[p*2] = min(ri[p*2],ri[p]);
}
}
if(li[p*2+1]==-1){
li[p*2+1] = li[p];
ri[p*2+1] = ri[p];
}else{
if(ri[p*2+1]<li[p]){
li[p*2+1] = li[p];
ri[p*2+1] = li[p];
}else if(ri[p]<li[p*2+1]){
li[p*2+1] = ri[p];
ri[p*2+1] = ri[p];
}else{
li[p*2+1] = max(li[p*2+1],li[p]);
ri[p*2+1] = min(ri[p*2+1],ri[p]);
}
}
}
li[p] = -1 , ri[p] = -1;
}
void update(int p,int l,int r,int lq,int rq,int ll,int rr){
prop(p,l,r);
if(l>=lq&&r<=rq){
li[p]=ll;
ri[p]=rr;
prop(p,l,r);
return ;
}
if(l>rq||r<lq)return ;
int md = (l+r)/2;
update(p*2,l,md,lq,rq,ll,rr);
update(p*2+1,md+1,r,lq,rq,ll,rr);
}
vector<int> ans;
void dfs(int p,int l,int r){
prop(p,l,r);
if(l==r){
ans.push_back(seg[p]);
return ;
}
int md = (l+r)/2;
dfs(p*2,l,md);
dfs(p*2+1,md+1,r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
memset(li,-1,sizeof li);
memset(ri,-1,sizeof ri);
build(1,1,n);
for(int i = 0;i<k;i++){
if(op[i]==1){
update(1,1,n,left[i]+1,right[i]+1,height[i],1e9);
}else{
update(1,1,n,left[i]+1,right[i]+1,0,height[i]);
}
ans.clear();
}
dfs(1,1,n);
for(int i = 0;i<n;i++){
finalHeight[i] = ans[i];
}
}
/*
int main(){
int op[] = {1,2,2,1,1,2};
int height[] = {4,1,5,3,5,0};
int left[] = {1,4,3,0,2,6};
int right[] = {8,9,6,5,2,7};
buildWall(10,6,op,left,right,height);
return 0;
}
*/
