#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2000009;
int ma[4*N];
int a[4*N];
int mi[4*N];
void build(int l,int r,int p){
ma[p]=200000;
mi[p]=0;
a[p]=0;
if(l==r){
return;
}
build(l,(l+r)/2,p*2);
build((l+r)/2+1,r,p*2+1);
return;
}
void setla(int l,int r,int p){
if(l==r)
return;
if((l+r)/2-l!=0){
ma[p*2]=max(ma[p*2],mi[p]);
mi[p*2]=min(mi[p*2],ma[p]);
ma[p*2]=min(ma[p],ma[p*2]);
mi[p*2]=max(mi[p*2],mi[p]);
}else{
if(a[p*2]>ma[p])
a[p*2]=ma[p];
if(a[p*2]<mi[p])
a[p*2]=mi[p];
}
if((l+r)/2+1!=r){
ma[p*2+1]=max(ma[p*2+1],mi[p]);
mi[p*2+1]=min(mi[p*2+1],ma[p]);
ma[p*2+1]=min(ma[p],ma[p*2+1]);
mi[p*2+1]=max(mi[p*2+1],mi[p]);
}else{
if(a[p*2+1]>ma[p])
a[p*2+1]=ma[p];
if(a[p*2+1]<mi[p])
a[p*2+1]=mi[p];
}
ma[p]=200000;
mi[p]=0;
return;
}
void upre(int x,int y,int h,int l,int r,int p){
setla(l,r,p);
if(x==l&&l==r){
if(a[p]>h)
a[p]=h;
return;
}
if(y<l||x>r)
return;
if(r<=y&&l>=r){
ma[p]=h;
setla(l,r,p);
return;
}
upre(x,y,h,l,(l+r)/2,p*2);
upre(x,y,h,(l+r)/2+1,r,p*2+1);
return;
}
void upad(int x,int y,int h,int l,int r,int p){
setla(l,r,p);
if(x==l&&l==r){
if(a[p]<h)
a[p]=h;
return;
}
if(y<l||x>r)
return;
if(r<=y&&l>=r){
mi[p]=h;
setla(l,r,p);
return;
}
upad(x,y,h,l,(l+r)/2,p*2);
upad(x,y,h,(l+r)/2+1,r,p*2+1);
return;
}
vector<int> ans;
void over(int l,int r,int p){
setla(l,r,p);
if(l==r){
ans.push_back(a[p]);
return;
}
over(l,(l+r)/2,p*2);
over((l+r)/2+1,r,p*2+1);
return;
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
build(1,n,1);
for(int i=0;i<k;i++){
left[i]++;
right[i]++;
}
for(int i=0;i<k;i++){
if(op[i]-1){
upre(left[i],right[i],height[i],1,n,1);
}else{
upad(left[i],right[i],height[i],1,n,1);
}
}
over(1,n,1);
for(int i=0;i<n;i++)
finalHeight[i]=ans[i];
return;
}
