#include<bits/stdc++.h>
using namespace std;
#include "wall.h"
const int maxn=4e6+1;
int t[2*maxn],L[2*maxn],R[2*maxn],propmx[2*maxn],propmn[2*maxn];
inline void build(int x,int tl,int tr){
L[x]=tl;
R[x]=tr;
propmn[x]=1e9;
propmx[x]=-1e9;
if(tl+1==tr)return;
int m=(L[x]+R[x])/2;
build(2*x+1,tl,m);
build(2*x+2,m,tr);
}
inline void applymn(int x,int v){
propmx[x]=min(propmx[x],v);
propmn[x]=min(propmn[x],v);
t[x]=min(t[x],v);
}
inline void applymx(int x,int v){
propmx[x]=max(propmx[x],v);
propmn[x]=max(propmn[x],v);
t[x]=max(t[x],v);
}
inline void push(int x){
int lp=2*x+1,rp=2*x+2;
applymn(lp,propmn[x]);
applymn(rp,propmn[x]);
propmn[x]=1e9;
applymx(lp,propmx[x]);
applymx(rp,propmx[x]);
propmx[x]=-1e9;
}
inline void updmn(int x,int a,int b,int v){
int l=L[x],r=R[x];
if(r<=a || b<=l)
return;
else if(a<=l && r<=b){
applymn(x,v);
return;
}
push(x);
updmn(2*x+1,a,b,v);
updmn(2*x+2,a,b,v);
}
inline void updmx(int x,int a,int b,int v){
int l=L[x],r=R[x];
if(r<=a || b<=l)
return;
else if(a<=l && r<=b){
applymx(x,v);
return;
}
push(x);
updmx(2*x+1,a,b,v);
updmx(2*x+2,a,b,v);
}
inline int qur(int i,int x){
int l=L[x],r=R[x];
int m=(l+r)/2;
if(l+1==r)
return t[x];
push(x);
if(i<m)
return qur(i,2*x+1);
else
return qur(i,2*x+2);
}
void buildWall(int n, int k, int op[], int LL[], int RR[], int H[], int ans[]){
build(0,0,n);
for(int i=0; i<k; i++){
if(op[i]==1)
updmx(0,LL[i],RR[i] +1,H[i]);
else
updmn(0,LL[i],RR[i] +1,H[i]);
}
for(int i=0; i<n; i++)
ans[i]=qur(i,0);
}
