#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
vector<int> tree, mx, mn;
vector<bool> has;
void push(int i, int L, int R) {
if (L == R || !has[i]) return;
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
has[i] = false;
has[x] = has[y] = true;
mn[x] = mx[x] = mn[y] = mx[y] = tree[x] = tree[y] = tree[i];
}
void build(int i, int L, int R) {
if (L == R) {
tree[i] = mx[i] = mn[i] = 0;
has[i] = false;
return;
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
build(x, L, m);
build(y, m + 1, R);
mx[i] = max(mx[x], mx[y]);
mn[i] = min(mn[x], mn[y]);
}
void add(int i, int L, int R, int l, int r, int v) {
if (L == R) {
tree[i] = max(tree[i], v);
mn[i] = mx[i] = tree[i];
has[i] = true;
return;
}
if (mn[i] >= v) return;
if (L == l && R == r && mx[i] <= v) {
tree[i] = mn[i] = mx[i] = v;
has[i] = true;
return;
}
push(i, L, R);
int m = (L + R) >> 1, x = 2 * i + 1, y = x + 1;
if (r <= m) {
add(x, L, m, l, r, v);
} else if (l > m) {
add(y, m + 1, R, l, r, v);
} else {
add(x, L, m, l, m, v);
add(y, m + 1, R, m + 1, r, v);
}
mx[i] = max(mx[x], mx[y]);
mn[i] = min(mn[x], mn[y]);
}
void remove(int i, int L, int R, int l, int r, int v) {
if (L == R) {
tree[i] = min(tree[i], v);
mn[i] = mx[i] = tree[i];
has[i] = true;
return;
}
if (mx[i] <= v) return;
if (L == l && R == r && mn[i] >= v) {
tree[i] = mn[i] = mx[i] = v;
has[i] = true;
return;
}
push(i, L, R);
int m = (L + R) >> 1, x = 2 * i + 1, y = x + 1;
if (r <= m) {
remove(x, L, m, l, r, v);
} else if (l > m) {
remove(y, m + 1, R, l, r, v);
} else {
remove(x, L, m, l, m, v);
remove(y, m + 1, R, m + 1, r, v);
}
mx[i] = max(mx[x], mx[y]);
mn[i] = min(mn[x], mn[y]);
}
int query(int i, int L, int R, int p) {
if (L == R) {
return tree[i];
}
push(i, L, R);
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (p <= m) {
return query(x, L, m, p);
} else {
return query(y, m + 1, R, p);
}
}
void buildWall(int n, int k, int op[], int l_[], int r_[], int h_[], int res[]) {
tree.resize(4 * n + 5, 0);
mx.resize(4 * n + 5, 0);
mn.resize(4 * n + 5, 0);
has.resize(4 * n + 5, false);
for (int x = 0; x < k; ++x) {
int q = op[x];
int l = l_[x], r = r_[x], h = h_[x];
if (q == 1) {
add(0, 0, n - 1, l, r, h);
} else {
remove(0, 0, n - 1, l, r, h);
}
}
for (int i = 0; i < n; ++i) {
res[i] = query(0, 0, n - 1, i);
}
}
