#include <wall.h>
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const int MAX = 2000020;
int n, k;
pair<int, int> st[(1 << 22) + 5];
void build(int id, int l, int r) {
st[id] = make_pair(+INF, -INF);
if (l == r) {
st[id] = make_pair(+INF, 0);
return;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
void pushMax(int id, int h) {
st[id].first = max(st[id].first, h); st[id].second = max(st[id].second, h);
}
void pushMin(int id, int h) {
st[id].first = min(st[id].first, h); st[id].second = min(st[id].second, h);
}
void push(int id) {
if (st[id].first != +INF) {
pushMin(id << 1, st[id].first);
pushMin(id << 1 | 1, st[id].first);
}
if (st[id].second != -INF) {
pushMax(id << 1, st[id].second);
pushMax(id << 1 | 1, st[id].second);
}
st[id] = make_pair(+INF, -INF);
}
void update(int id, int l, int r, int u, int v, int h, int t) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
if (!t) pushMax(id, h);
else pushMin(id, h);
return;
}
push(id);
int mid = l + r >> 1;
update(id << 1, l, mid, u, v, h, t);
update(id << 1 | 1, mid + 1, r, u, v, h, t);
}
void getAns(int id, int l, int r, int ans[]) {
if (l == r) ans[l] = st[id].second;
else {
push(id);
int mid = l + r >> 1;
getAns(id << 1, l, mid, ans);
getAns(id << 1 | 1, mid + 1, r, ans);
}
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
n = N, k = K;
build(1, 0, n - 1);
for (int i = 0; i < k; ++i) {
update(1, 0, n - 1, left[i], right[i], height[i], op[i] - 1);
}
getAns(1, 0, n - 1, finalHeight);
}
