// mrrrow mnyaa ;3c
// go play vivid/stasis! it's a really awesome free game on steam
const int N = 1 << 21;
int st[N * 2][3];
void merge(int i, int a, int b) {
if (st[i][0]) {
st[i][1] = st[i][1] <= a ? a : st[i][1] >= b ? b : st[i][1];
st[i][2] = st[i][2] <= a ? a : st[i][2] >= b ? b : st[i][2];
} else {
st[i][0] = true;
st[i][1] = a;
st[i][2] = b;
}
}
void push(int i) {
if (!st[i][0]) return;
st[i][0] = false;
merge(i * 2, st[i][1], st[i][2]);
merge(i * 2 + 1, st[i][1], st[i][2]);
}
void update(int a, int b, int l, int r, int i = 1, int cl = 0, int cr = N - 1) {
if (l <= cl && cr <= r) {
merge(i, a, b);
return;
}
push(i);
int me = (cl + cr) / 2;
int ms = me + 1;
if (l <= me && cl <= r) update(a, b, l, r, i * 2, cl, me);
if (l <= cr && ms <= r) update(a, b, l, r, i * 2 + 1, ms, cr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (int it = 0; it < k; it++)
update(op[it] == 1 ? height[it] : -0x80000000, op[it] == 2 ? height[it] : 0x7fffffff, left[it], right[it]);
for (int i = 0; i < n; i++) {
for (int j = N + i; j; j /= 2) {
if (st[j][0]) {
finalHeight[i] = finalHeight[i] <= st[j][1] ? st[j][1] : finalHeight[i] >= st[j][2] ? st[j][2] : finalHeight[i];
}
}
}
}
