#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
void chmin (int &x, int y) {
x = min(x, y);
}
void chmax(int &x, int y) {
x = max(x, y);
}
struct pp {
int mx = 0, mn = 1e9;
};
struct SegmentTree {
vector <pp> tree;
void prop (int l, int r, int node) {
if (l == r) return;
chmin(tree[tl].mn, tree[node].mn);
chmax(tree[tl].mn, tree[node].mx);
chmax(tree[tl].mx, tree[node].mx);
chmin(tree[tl].mx, tree[node].mn);
chmin(tree[tr].mn, tree[node].mn);
chmax(tree[tr].mn, tree[node].mx);
chmax(tree[tr].mx, tree[node].mx);
chmin(tree[tr].mx, tree[node].mn);
tree[node].mn = 1e9; tree[node].mx = 0;
}
void update (int l, int r, int a, int b, int h, int t, int node) {
prop(l, r, node);
if (l > b || r < a) return;
if (l >= a && r <= b) {
if (t == 2) {
chmin(tree[node].mn, h);
chmin(tree[node].mx, h);
} else {
chmax(tree[node].mn, h);
chmax(tree[node].mx, h);
}
prop(l, r, node);
return;
}
update(l, mid, a, b, h, t, tl);
update(mid + 1, r, a, b, h, t, tr);
}
void dfs (int l, int r, int node) {
prop(l, r, node);
if (l == r) return;
dfs(l, mid, tl);
dfs(mid + 1, r, tr);
}
pp get (int l, int r, int a, int node) {
if (l == r) {
return tree[node];
}
if (mid < a) return get(mid + 1, r, a, tr);
return get(l, mid, a, tl);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegmentTree cur; cur.tree.resize(2 * n);
for (int i = 0; i < k; i++) {
left[i]++; right[i]++;
}
for (int i = 0; i < k; i++) {
cur.update(1, n, left[i], right[i], height[i], op[i], 1);
}
cur.dfs(1, n, 1);
for (int i = 0; i < n; i++) {
auto k = cur.get(1, n, i + 1, 1);
finalHeight[i] = min(k.mn, k.mx);
}
}
