#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
using namespace std;
struct Node{
int mn,mx,val;
bool uniform;
};
vector<Node> seg;
int N;
void build(int idx,int l,int r){
if(l==r){seg[idx]={0,0,0,true};return;}
int mid=(l+r)/2;
build(idx*2,l,mid);
build(idx*2+1,mid+1,r);
seg[idx]={0,0,0,true};
}
void pushDown(int idx,int l,int r){
if(!seg[idx].uniform||l==r)return;
int mid=(l+r)/2;
seg[idx*2]={seg[idx].val,seg[idx].val,seg[idx].val,true};
seg[idx*2+1]={seg[idx].val,seg[idx].val,seg[idx].val,true};
seg[idx].uniform=false;
}
void update(int idx,int l,int r,int ql,int qr,int op,int h){
if(ql>r||qr<l)return;
if(ql<=l&&r<=qr){
if(op==1){
if(seg[idx].mn>=h)return;
if(seg[idx].mx<h){seg[idx]={h,h,h,true};return;}
}else{
if(seg[idx].mx<=h)return;
if(seg[idx].mn>h){seg[idx]={h,h,h,true};return;}
}
}
pushDown(idx,l,r);
int mid=(l+r)/2;
update(idx*2,l,mid,ql,qr,op,h);
update(idx*2+1,mid+1,r,ql,qr,op,h);
seg[idx].mn=min(seg[idx*2].mn,seg[idx*2+1].mn);
seg[idx].mx=max(seg[idx*2].mx,seg[idx*2+1].mx);
if(seg[idx*2].uniform&&seg[idx*2+1].uniform&&seg[idx*2].val==seg[idx*2+1].val)
seg[idx]={seg[idx*2].val,seg[idx*2].val,seg[idx*2].val,true};
else seg[idx].uniform=false;
}
void query(int idx,int l,int r,vector<int>& ans){
if(l==r){ans[l]=seg[idx].uniform?seg[idx].val:seg[idx].mn;return;}
pushDown(idx,l,r);
int mid=(l+r)/2;
query(idx*2,l,mid,ans);
query(idx*2+1,mid+1,r,ans);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
N=n;
seg.assign(4*n,{0,0,0,true});
build(1,0,n-1);
for(int i=0;i<k;i++){
update(1,0,n-1,left[i],right[i],op[i],height[i]);
}
vector<int> ans(n,0);
query(1,0,n-1,ans);
for(int i=0;i<n;i++)finalHeight[i]=ans[i];
}
