#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int mxn = 2e6 + 5, inf = 0x3f3f3f3f;
int n, _1[mxn * 4], _2[mxn * 4];
void apply(int i, int v1, int v2) {
_1[i] = max(v1, min(_1[i], v2));
_2[i] = min(v2, max(_1[i], v1));
}
void push(int i) {
apply(2 * i, _1[i], _2[i]);
apply(2 * i + 1, _1[i], _2[i]);
_1[i] = inf;
_2[i] = 0;
}
void upd(int ql, int qr, int v1, int v2, int i = 1, int tl = 0, int tr = n - 1) {
if (ql > tr || qr < tl) return;
if (ql <= tl && tr <= qr) {
apply(i, v1, v2);
return;
}
push(i);
int mid = tl + tr >> 1;
upd(ql, qr, v1, v2, 2 * i, tl, mid);
upd(ql, qr, v1, v2, 2 * i + 1, mid + 1, tr);
}
void fillans(int *ans, int i = 1, int tl = 0, int tr = n - 1) {
if (tl == tr) {
ans[tl] = min(_1[i], _2[i]);
return;
}
push(i);
int mid = tl + tr >> 1;
fillans(ans, 2 * i, tl, mid);
fillans(ans, 2 * i + 1, mid + 1, tr);
}
void buildWall(int len, int k, int *op, int *left, int *right, int *height, int *ans) {
n = len;
for (int i = 0; i < k; i++) {
upd(left[i], right[i], op[i] == 1 ? height[i] : inf, op[i] == 2 ? height[i] : 0);
}
fillans(ans);
}
