#include<bits/stdc++.h>
#include "wall.h"
#define MAXN 2000007
using namespace std;
int n,q;
int s[MAXN];
struct ST{
struct node{
int mins,maxs;
int lazy;
inline friend node operator + (node fr,node sc){
return {min(fr.mins,sc.mins),max(fr.maxs,sc.maxs),-1};
}
};
node tree[4*MAXN];
void psh(int v){
if(tree[v].lazy==-1)return;
tree[2*v].maxs=tree[2*v].mins=tree[2*v].lazy=tree[v].lazy;
tree[2*v+1].maxs=tree[2*v+1].mins=tree[2*v+1].lazy=tree[v].lazy;
tree[v].lazy=-1;
}
void add(int v,int l,int r,int ll,int rr,int val){
if(ll>rr)return;
if(l==ll and r==rr and tree[v].maxs==tree[v].mins){
if(tree[v].maxs<val){
tree[v].maxs=tree[v].mins=val;
tree[v].lazy=val;
}
return;
}
int tt=(l+r)/2;
psh(v);
add(2*v,l,tt,ll,min(tt,rr),val);
add(2*v+1,tt+1,r,max(tt+1,ll),rr,val);
tree[v]=tree[2*v]+tree[2*v+1];
}
void rem(int v,int l,int r,int ll,int rr,int val){
if(ll>rr)return;
if(l==ll and r==rr and tree[v].maxs==tree[v].mins){
if(tree[v].maxs>val){
tree[v].maxs=tree[v].mins=val;
tree[v].lazy=val;
}
return;
}
int tt=(l+r)/2;
psh(v);
rem(2*v,l,tt,ll,min(tt,rr),val);
rem(2*v+1,tt+1,r,max(tt+1,ll),rr,val);
tree[v]=tree[2*v]+tree[2*v+1];
}
void solve(int v,int l,int r){
if(l==r){
s[l]=tree[v].maxs;
}else{
int tt=(l+r)/2;
psh(v);
solve(2*v,l,tt);
solve(2*v+1,tt+1,r);
}
}
}seg;
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
//void buildWall(int N, int K, vector<int> op,vector<int> left, vector<int> right, vector<int> height){
n=N; q=K;
for(int i=0;i<q;i++){
left[i]++;
right[i]++;
if(op[i]==1){
seg.add(1,1,n,left[i],right[i],height[i]);
}else{
seg.rem(1,1,n,left[i],right[i],height[i]);
}
}
seg.solve(1,1,n);
for(int i=1;i<=n;i++){
finalHeight[i-1]=s[i];
}
return;
}
/*int main(){
buildWall(10,6,{1,2,2,1,1,2},{1,4,3,0,2,6},{8,9,6,5,2,7},{4,1,5,3,5,0});
return 0;
}*/
