#include "bits/stdc++.h"
#ifndef LOCAL
#include "wall.h"
#endif
using namespace std;
struct item{
int l, r;
item(int l = 0, int r = INT_MAX) : l(l), r(r) {}
};
struct SegmentTree{
vector<item> st;
SegmentTree(int n) : st(n << 2) {}
void apply(int id, const item& val){
st[id].l = max(st[id].l, val.l);
st[id].l = min(st[id].l, val.r);
st[id].r = max(st[id].r, val.l);
st[id].r = min(st[id].r, val.r);
}
void lazyDown(int id){
apply(id << 1, st[id]);
apply(id << 1 | 1, st[id]);
st[id] = item();
}
void update(int id, int l, int r, int u, int v, const item& val){
if(u <= l && r <= v){
apply(id, val);
} else{
int mid = l + r >> 1;
lazyDown(id);
if(u <= mid) update(id << 1, l, mid, u, v, val);
if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
}
}
item query(int id, int l, int r, int k){
if(l == r) return st[id];
int mid = l + r >> 1;
lazyDown(id);
if(k <= mid) return query(id << 1, l, mid, k);
else return query(id << 1 | 1, mid + 1, r, k);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegmentTree T(n);
for(int i = 0; i < k; ++i){
if(op[i] == 1){
T.update(1, 0, n - 1, left[i], right[i], {height[i], INT_MAX});
} else{
T.update(1, 0, n - 1, left[i], right[i], {0, height[i]});
}
}
for(int i = 0; i < n; ++i){
finalHeight[i] = T.query(1, 0, n - 1, i).l;
}
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n = 10, k = 6;
int op[] = {1, 2, 2, 1, 1, 2}, left[] = {1, 4, 3, 0, 2, 6}, right[] = {8, 9, 6, 5, 2, 7}, height[] = {4, 1, 5, 3, 5, 0};
int finalHeight[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
buildWall(n, k, op, left, right, height, finalHeight);
for(int i = 0; i < n; ++i){
cout << finalHeight[i] << ' ';
}
cout << '\n';
return 0;
}
#endif
