#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long int;
struct SGT{
int t[(int)8e6][2] = {{0, (int)2e9}};
int n;
int ofs;
SGT(int sz){
n= sz;
ofs = 1ll<<(int)(ceil(log2(n+1)));
}
void apply(int p){
if (t[p][0]>t[2*p][1]) t[2*p][0]=t[p][0],t[2*p][1]=t[p][0]; else
if (t[2*p][0]>t[p][1]) t[2*p][0]=t[p][1], t[2*p][1]=t[p][1]; else
t[2*p][0]=max(t[2*p][0],t[p][0]), t[2*p][1]=min(t[2*p][1], t[p][1]);
if (t[p][0]>t[2*p+1][1]) t[2*p+1][0]=t[p][0],t[2*p+1][1]=t[p][0]; else
if (t[2*p+1][0]>t[p][1]) t[2*p+1][0]=t[p][1], t[2*p+1][1]=t[p][1]; else
t[2*p+1][0]=max(t[2*p+1][0],t[p][0]), t[2*p+1][1]=min(t[2*p+1][1], t[p][1]);
t[p][0] = 0; t[p][1] = (int)2e9;
}
void update(int p, int tl, int tr, int l ,int r, int h, int o){
if (p<ofs) apply(p);
if (l>r) return;
if (tl==l && tr==r){
if (o==0){
t[p][0] = max(t[p][0], h); t[p][1] = max(t[p][1], t[p][0]);
} else {
t[p][1] = min(t[p][1], h); t[p][0] = min(t[p][0], t[p][1]);
}
return;
}
int tm = (tl+tr)>>1;
update(2*p, tl, tm, l, min(tm, r), h, o);
update(2*p+1, tm+1, tr, max(l,tm+1), r, h, o);
}
void update(int l, int r, int h, int o){
update(1, 0, ofs-1, l, r, h, o);
}
void push(){
for (int i=1; i<ofs; i++){
apply(i);
}
}
};
void buildWall(int n, int k, int op[], int l[],int r[],int h[], int ans[]){
SGT st(n);
for (int i=0; i<k; i++){
st.update(l[i], r[i], h[i], op[i]-1);
}
st.push();
for (int i=0; i<n; i++) ans[i] = min(st.t[i+st.ofs][0], st.t[i+st.ofs][1]);
}
