#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define overload4(a, b, c, d, name, ...) name
#define rep1(i, n) for(ll i = 0; i < (n); ++i)
#define rep2(i, a, b) for(ll i = (a); i < (b); ++i)
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(i, n) for(ll i = (n) - 1; i >= 0; --i)
#define per2(i, a, b) for(ll i = (b) - 1; i >= a; --i)
#define per3(i, a, b, c) for(ll i = (b) - 1; i >= (a); i -= (c))
#define per(...) overload4(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define pb emplace_back
#define lb(v,k) (ll) (lower_bound(all(v), (k)) - v.begin())
#define ub(v,k) (ll) (upper_bound(all(v), (k)) - v.begin())
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T, vector<T>, greater<T>>
typedef long long ll;
typedef pair<ll,ll> P;
using vi = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;
using vp = vector<P>;
using vvp = vector<vp>;
constexpr ll inf = (ll) 1e9;
constexpr int _ = (int) 1e7;
ll mx[_], mn[_], tag[_];
vi res;
void apply(ll p, ll h) {
mx[p] = mn[p] = tag[p] = h;
}
void push(ll p) {
if (tag[p] != -1) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = -1;
}
}
void pull(ll p) {
mx[p] = max(mx[2 * p], mx[2 * p + 1]);
mn[p] = min(mn[2 * p], mn[2 * p + 1]);
}
void Add(ll p, ll l, ll r, ll ql, ll qr, ll h) {
if (r < ql || l > qr) return;
if (ql <= l && r <= qr) {
if (mx[p] <= h) { apply(p, h); return; }
if (mn[p] >= h) return;
if (l == r) return;
}
ll m = (l + r) / 2;
push(p);
Add(2 * p, l, m, ql, qr, h);
Add(2 * p + 1, m + 1, r, ql, qr, h);
pull(p);
}
void Remove(ll p, ll l, ll r, ll ql, ll qr, ll h) {
if (r < ql || l > qr) return;
if (ql <= l && r <= qr) {
if (mn[p] >= h) { apply(p, h); return; }
if (mx[p] <= h) return;
if (l == r) return;
}
ll m = (l + r) / 2;
push(p);
Remove(2 * p, l, m, ql, qr, h);
Remove(2 * p + 1, m + 1, r, ql, qr, h);
pull(p);
}
void traversal(ll p, ll l, ll r) {
if (l == r) {
res.pb(mn[p]);
return;
}
ll m = (l + r) / 2;
push(p);
traversal(2 * p, l, m);
traversal(2 * p + 1, m + 1, r);
}
void buildWall(int n, int k, int t[], int l[], int r[], int h[], int ans[]) {
rep(p, _) tag[p] = -1;
rep(i, k) {
if (t[i] == 1) Add(1, 0, n - 1, l[i], r[i], h[i]);
else Remove(1, 0, n - 1, l[i], r[i], h[i]);
}
traversal(1, 0, n - 1);
rep(i, n) ans[i] = res[i];
}
