#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{
int n;
vector<int>treeMin,treeMax,lazyMin,lazyMax;
SegmentTree(int size){
n=size;
treeMin.resize(4*n,INT_MAX);
treeMax.resize(4*n,-INT_MAX);
lazyMin.resize(4*n,-1);
lazyMax.resize(4*n,-1);
}
void propagate(int node,int start,int end){
if(lazyMin[node]!=-1){
treeMin[node]=min(treeMin[node],lazyMin[node]);
if(start!=end){
lazyMin[2*node+1]=(lazyMin[2*node+1]==-1)?lazyMin[node]:min(lazyMin[2*node+1],lazyMin[node]);
lazyMin[2*node+2]=(lazyMin[2*node+2]==-1)?lazyMin[node]:min(lazyMin[2*node+2],lazyMin[node]);
}
lazyMin[node]=-1;
}
if(lazyMax[node]!=-1){
treeMax[node]=max(treeMax[node],lazyMax[node]);
if(start!=end){
lazyMax[2*node+1]=(lazyMax[2*node+1]==-1)?lazyMax[node]:max(lazyMax[2*node+1],lazyMax[node]);
lazyMax[2*node+2]=(lazyMax[2*node+2]==-1)?lazyMax[node]:max(lazyMax[2*node+2],lazyMax[node]);
}
lazyMax[node]=-1;
}
}
void update2Range(int node,int start,int end,int l,int r,int value){
propagate(node,start,end);
if(start>end||start>r||end<l)return;
if(start>=l&&end<=r){
lazyMin[node]=(lazyMin[node]==-1)?value:min(lazyMin[node],value);
propagate(node,start,end);
return;
}
int mid=(start+end)/2;
update2Range(2*node+1,start,mid,l,r,value);
update2Range(2*node+2,mid+1,end,l,r,value);
treeMin[node]=min(treeMin[2*node+1],treeMin[2*node+2]);
}
void update1Range(int node,int start,int end,int l,int r,int value){
propagate(node,start,end);
if(start>end||start>r||end<l)return;
if(start>=l&&end<=r){
lazyMax[node]=(lazyMax[node]==-1)?value:max(lazyMax[node],value);
propagate(node,start,end);
return;
}
int mid=(start+end)/2;
update1Range(2*node+1,start,mid,l,r,value);
update1Range(2*node+2,mid+1,end,l,r,value);
treeMax[node]=max(treeMax[2*node+1],treeMax[2*node+2]);
}
int queryMin(int node,int start,int end,int l,int r){
propagate(node,start,end);
if(start>end||start>r||end<l)return INT_MAX;
if(start>=l&&end<=r)return treeMin[node];
int mid=(start+end)/2;
int left_query=queryMin(2*node+1,start,mid,l,r);
int right_query=queryMin(2*node+2,mid+1,end,l,r);
return min(left_query,right_query);
}
int queryMax(int node,int start,int end,int l,int r){
propagate(node,start,end);
if(start>end||start>r||end<l)return -INT_MAX;
if(start>=l&&end<=r)return treeMax[node];
int mid=(start+end)/2;
int left_query=queryMax(2*node+1,start,mid,l,r);
int right_query=queryMax(2*node+2,mid+1,end,l,r);
return max(left_query,right_query);
}
void update2(int l,int r,int value){
update2Range(0,0,n-1,l,r,value);
}
void update1(int l,int r,int value){
update1Range(0,0,n-1,l,r,value);
}
int rangeQueryMin(int l,int r){
return queryMin(0,0,n-1,l,r);
}
int rangeQueryMax(int l,int r){
return queryMax(0,0,n-1,l,r);
}
};
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
SegmentTree st(n);
for(int i=0;i<k;++i){
int l=left[i], r=right[i], value = height[i];
if(op[i] == 1){
st.update1(l, r, value);
}
else if(op[i] == 2){
st.update2(l, r, value);
}
}
for(int i=0;i<n;++i){
finalHeight[i] = st.rangeQueryMin(i, i);
}
}
