#include <iostream>
#include <vector>
//#include "wall.h"
using namespace std;
struct node {
int L, M, R, MN, MX;
node() { MN = 0; MX = 1e5; }
};
vector <node> sgt(5e6, node());
vector <int> ans(2e6);
void build_sgt(int x, int l, int r) {
sgt[x].L = l;
sgt[x].M = (l + r) / 2;
sgt[x].R = r;
if (r - l == 1) { sgt[x].MX = 0; return; }
build_sgt(2 * x, l, (l + r) / 2);
build_sgt(2 * x + 1, (l + r) / 2, r);
}
void update_node(int x, int mn, int mx) {
if (mx < sgt[x].MN) { sgt[x].MN = sgt[x].MX = mx; return; }
if (mn > sgt[x].MX) { sgt[x].MN = sgt[x].MX = mn; return; }
sgt[x].MN = max(sgt[x].MN, mn);
sgt[x].MX = min(sgt[x].MX, mx);
}
void push_down(int x) {
if (sgt[x].R - sgt[x].L == 1) return;
update_node(2 * x, sgt[x].MN, sgt[x].MX);
update_node(2 * x + 1, sgt[x].MN, sgt[x].MX);
sgt[x].MN = 0;
sgt[x].MX = 1e5;
}
void update(int x, int l, int r, int mn, int mx) {
push_down(x);
if (r <= sgt[x].L || sgt[x].R <= l) return;
if (l <= sgt[x].L && sgt[x].R <= r) { update_node(x, mn, mx); return; }
update(2 * x, l, r, mn, mx);
update(2 * x + 1, l, r, mn, mx);
}
void get_ans(int x) {
if (sgt[x].R - sgt[x].L == 1) { ans[sgt[x].L] = sgt[x].MN; return; }
push_down(x);
get_ans(2 * x);
get_ans(2 * x + 1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
build_sgt(1, 0, n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) update(1, left[i], right[i] + 1, height[i], 1e5);
else update(1, left[i], right[i] + 1, 0, height[i]);
}
get_ans(1);
for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
}
