#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int inf=1e6;
struct node{
int mx,mn,mx2,mn2;
node(int _mx=-inf,int _mn=inf,int _mx2=-inf,int _mn2=inf){
mx=_mx,mx2=_mx2,mn=_mx,mn2=_mn2;
}
friend node operator+(node a,node b){
node c;
if(a.mx>b.mx)c.mx=a.mx,c.mx2=max(a.mx2,b.mx);
else if(b.mx>a.mx)c.mx=b.mx,c.mx2=max(a.mx,b.mx2);
else c.mx=a.mx,c.mx2=max(a.mx2,b.mx2);
if(a.mn<b.mn)c.mn=a.mn,c.mn2=min(a.mn2,b.mn);
else if(b.mn<a.mn)c.mn=b.mn,c.mn2=min(a.mn,b.mn2);
else c.mn=a.mn,c.mn2=min(a.mn2,b.mn2);
return c;
}
};
struct segtree_beats{
node info[8000005];
void chmx(int st,int en,int i,int val){
if(val<info[i].mn)return;
info[i].mn=val;
if(val>=info[i].mx)info[i].mx=val;
else if(val>info[i].mx2)info[i].mx2=val;
}
void chmn(int st,int en,int i,int val){
if(val>info[i].mx)return;
info[i].mx=val;
if(val<=info[i].mn)info[i].mn=val;
else if(val<info[i].mn2)info[i].mn2=val;
}
void push(int st,int en,int i){
int m=(st+en)/2;
chmx(st,m,i*2,info[i].mn);
chmx(m+1,en,i*2+1,info[i].mn);
chmn(st,m,i*2,info[i].mx);
chmn(m+1,en,i*2+1,info[i].mx);
}
void chmax(int st,int en,int i,int l,int r,int val){
if(st>r||en<l||val<=info[i].mn)return;
//cerr<<st<<" "<<en<<"\n";
if(st>=l&&en<=r&&val<info[i].mn2){
chmx(st,en,i,val);
//cerr<<"change mn into:"<<info[i].mn<<" "<<info[i].mx<<"\n";
return;
}
int m=(st+en)/2;
push(st,en,i);
chmax(st,m,i*2,l,r,val);
chmax(m+1,en,i*2+1,l,r,val);
info[i]=info[i*2]+info[i*2+1];
//cerr<<st<<' '<<en<<" turns into "<<info[i].mn<<" "<<info[i].mn2<<" "<<info[i].mx<<" "<<info[i].mx2<<"\n";
}
void chmin(int st,int en,int i,int l,int r,int val){
if(st>r||en<l||val>=info[i].mx)return;
if(st>=l&&en<=r&&val>info[i].mx2)return chmn(st,en,i,val);
int m=(st+en)/2;
push(st,en,i);
chmin(st,m,i*2,l,r,val);
chmin(m+1,en,i*2+1,l,r,val);
info[i]=info[i*2]+info[i*2+1];
}
int fans(int st,int en,int i,int pos){
if(st==en)return info[i].mx;
push(st,en,i);
int m=(st+en)/2;
if(pos<=m)return fans(st,m,i*2,pos);
else return fans(m+1,en,i*2+1,pos);
}
void build(int st,int en,int i){
info[i]=node(0,0);
if(st==en)return;
int m=(st+en)/2;
build(st,m,i*2);
build(m+1,en,i*2+1);
}
}tr;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
tr.build(1,n,1);
//cerr<<"work\n";
for(int i=0;i<k;i++){
if(op[i]==1){
//cerr<<"chmax\n";
tr.chmax(1,n,1,left[i]+1,right[i]+1,height[i]);
}else{
//cerr<<"chmin\n";
tr.chmin(1,n,1,left[i]+1,right[i]+1,height[i]);
}
//cerr<<"mx:"<<tr.info[1].mx<<"\n";
//for(int i=1;i<=n;i++)cerr<<tr.fans(1,n,1,i)<<" ";
//cerr<<"\n";
}
//cerr<<"work\n";
for(int i=1;i<=n;i++){
finalHeight[i-1]=tr.fans(1,n,1,i);
//cerr<<finalHeight[i-1]<<" ";
}
return;
}
