#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>ans;
struct seg{
int mn,mx,l,r;
seg *lf,*rg;
void build(int x,int y){
l=x,r=y;
mn=mx=0;
if(l==r){
return;
}
int mid=(l+r)/2;
lf=new seg(),rg=new seg();
lf->build(l,mid),rg->build(mid+1,r);
}
void apply(int mini,int maxi){
mn=min(max(mn,mini),maxi);
mx=max(min(mx,maxi),mini);
}
void prop(){
if(l==r)return;
lf->apply(mn,mx),rg->apply(mn,mx);
}
void update(int posl,int posr,int op,int brp){
if(l>posr || r<posl)return;
if(l>=posl && r<=posr){
if(op==1){
mn=max(mn,brp);
mx=max(mx,brp);
}
else{
mn=min(mn,brp);
mx=min(mx,brp);
}
return;
}
prop();
lf->update(posl,posr,op,brp),rg->update(posl,posr,op,brp);
mn=min(lf->mn,rg->mn);
mx=max(lf->mx,rg->mx);
}
void solve(int l,int r){
if(l==r){
ans[l]=mn;
return;
}
prop();
int mid=(l+r)/2;
lf->solve(l,mid),rg->solve(mid+1,r);
}
};
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n=N;
ans=vector<int>(n+1,0);
seg apa; apa.build(0,n-1);
for(int q=0;q<k;q++){
apa.update(left[q],right[q],op[q],height[q]);
}
apa.solve(0,n-1);
for(int q=0;q<n;q++){
finalHeight[q]=ans[q];
}
return;
}
