#include <wall.h>
#include <bits/stdc++.h>
#define ll long long
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 2e6 + 11;
int kp[N * 4];
int mn[N * 4], mx[N * 4];
void push(int u) {
if(kp[u] == -1) return;
mn[ls] = mn[rs] = kp[u];
mx[ls] = mx[rs] = kp[u];
kp[ls] = kp[rs] = kp[u];
kp[u] = -1;
}
void add(int ql,int qr,int x,int u,int l,int r) {
if(ql > r || l > qr || mn[u] >= x) return;
if(ql <= l && r <= qr) {
if(mx[u] <= x) {
mn[u] = mx[u] = x;
kp[u] = x;
return;
}
}
push(u);
int m = l + r >> 1;
add(ql, qr, x, ls, l, m);
add(ql, qr, x, rs, m + 1, r);
mn[u] = min(mn[ls], mn[rs]);
mx[u] = max(mx[ls], mx[rs]);
}
void del(int ql,int qr,int x,int u,int l,int r) {
if(ql > r || l > qr || mx[u] <= x) return;
if(ql <= l && r <= qr) {
if(mn[u] >= x) {
mn[u] = mx[u] = x;
kp[u] = x;
return;
}
}
push(u);
int m = l + r >> 1;
del(ql, qr, x, ls, l, m);
del(ql, qr, x, rs, m + 1, r);
mn[u] = min(mn[ls], mn[rs]);
mx[u] = max(mx[ls], mx[rs]);
}
int get(int p,int u,int l,int r) {
if(l == r) {
return mn[u];
}
push(u);
int m = l + r >> 1;
if(p <= m) return get(p, ls, l, m);
else return get(p, rs, m + 1, r);
}
void buildWall(int n,int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
memset(kp, -1, sizeof(kp));
for(int i = 0; i < k; i++) {
int l = left[i], r = right[i], type = op[i], x = height[i];
if(type == 1) {
add(l, r, x, 1, 0, n - 1);
} else {
del(l, r, x, 1, 0, n - 1);
}
}
for(int i = 0; i < n; i++) {
finalHeight[i] = get(i, 1, 0, n - 1);
}
}
