#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 2000000;
struct SGTInfo {
int lazyMin, lazyMax;
SGTInfo () {
lazyMin = INT_MIN;
lazyMax = INT_MAX;
}
void update (int newMin, int newMax) {
if (newMax < lazyMin) {
lazyMin = lazyMax = newMax;
} else if (lazyMax < newMin) {
lazyMin = lazyMax = newMin;
} else {
lazyMin = max(lazyMin, newMin);
lazyMax = min(lazyMax, newMax);
}
}
};
SGTInfo SGT[N_MAX * 4 + 2];
void build (int node, int l, int r) {
SGT[node] = SGTInfo();
if (l == r) {
SGT[node].update(0, 0);
} else {
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
build(lSon, l, mid);
build(rSon, mid + 1, r);
}
}
void split (int node) {
int lSon = node * 2, rSon = node * 2 + 1;
SGT[lSon].update(SGT[node].lazyMin, SGT[node].lazyMax);
SGT[rSon].update(SGT[node].lazyMin, SGT[node].lazyMax);
SGT[node] = SGTInfo();
}
void update (int node, int l, int r, int ul, int ur, int utype, int uval) {
if (ul <= l && r <= ur) {
if (utype == 1) {
SGT[node].update(uval, INT_MAX);
} else {
SGT[node].update(INT_MIN, uval);
}
} else {
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
split(node);
if (ul <= mid) {
update(lSon, l, mid, ul, ur, utype, uval);
}
if (mid + 1 <= ur) {
update(rSon, mid + 1, r, ul, ur, utype, uval);
}
}
}
int answer[N_MAX];
void getAnswer (int node, int l, int r) {
if (l == r) {
answer[l] = SGT[node].lazyMin;
} else {
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
split(node);
getAnswer(lSon, l, mid);
getAnswer(rSon, mid + 1, r);
}
}
void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
build(1, 0, n - 1);
for (int i = 0; i < k; i++) {
update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
}
getAnswer(1, 0, n - 1);
copy(answer, answer + n, finalHeight);
}
