#include <bits/stdc++.h>
#define int long long
// #include "wall.h"
using namespace std;
void buildWall(int n, int q, vector<int> t, vector<int> left, vector<int> right, vector<int> h, vector<long long> a)
{
struct SEGMENT_TREE{
struct node{
int lo, hi;
bool inc;
inline node(){
lo = -1;
hi = 1e9;
inc = false;
}
}; vector<node> st;
inline SEGMENT_TREE(int n){
st.resize(4 * n);
}
inline void update_node(int ind, int h, int t, bool b){
st[ind].inc |= b;
if (t == 1){
st[ind].lo = max(st[ind].lo, h);
if (st[ind].lo > st[ind].hi) st[ind].hi = 1e9;
}
else{
st[ind].hi = min(st[ind].hi, h);
if (st[ind].hi < st[ind].lo) st[ind].lo = -1;
}
return;
}
inline void update(int ind, int l, int r, int lb, int rb, int h, int t){
if (l >= lb && r <= rb){
update_node(ind, h, t, (t == 1));
return;
}
if (st[ind].lo != -1)
update_node(ind << 1, st[ind].lo, 1, true), update_node(ind << 1 | 1, st[ind].lo, 1, true);
if (st[ind].hi != -1)
update_node(ind << 1, st[ind].hi, 2, st[ind].inc), update_node(ind << 1 | 1, st[ind].hi, 2, st[ind].inc);
st[ind] = node();
int mid = (l + r) >> 1;
if (mid >= lb) update(ind << 1, l, mid, lb, rb, h, t);
if (mid < rb) update(ind << 1 | 1, mid + 1, r, lb, rb, h, t);
return;
}
inline void get(int ind, int l, int r, vector<int>& a){
if (l == r){
if (a[l] < st[ind].lo) a[l] = st[ind].lo;
else if (a[l] > st[ind].hi) a[l] = st[ind].hi;
if (st[ind].lo == -1 && st[ind].hi != 1e9 && st[ind].inc) a[l] = st[ind].hi;
return;
}
if (st[ind].lo != -1)
update_node(ind << 1, st[ind].lo, 1, true), update_node(ind << 1 | 1, st[ind].lo, 1, true);
if (st[ind].hi != -1)
update_node(ind << 1, st[ind].hi, 2, st[ind].inc), update_node(ind << 1 | 1, st[ind].hi, 2, st[ind].inc);
st[ind] = node();
int mid = (l + r) >> 1;
get(ind << 1, l, mid, a);
get(ind << 1 | 1, mid + 1, r, a);
}
} seg(n);
for (int i = 0; i < q; ++i)
seg.update(1, 0, n - 1, left[i], right[i], h[i], t[i]);
seg.get(1, 0, n - 1, a);
for (int i : a) cout << i << " ";
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n = 10, q = 6;
vector<int> t = {1, 2, 2, 1, 1, 2};
vector<int> left = {1, 4, 3, 0, 2, 6};
vector<int> right = {8, 9, 6, 5, 2, 7};
vector<int> h = {4, 1, 5, 3, 5, 0};
vector<int> a(n, 0);
buildWall(n, q, t, left, right, h, a);
}
