#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, pair<int, int>> pii;
#define f first
#define s second
pii tree[8000010]; const int INF = 2e9;
bool ckmin(int& A, int B) { return (B < A) ? A = B, true : false; }
bool ckmax(int& A, int B) { return (B > A) ? A = B, true : false; }
void pushdown(int x, int l, int r) {
ckmin(tree[x].f, tree[x].s.f); ckmax(tree[x].f, tree[x].s.s);
if (l < r) for (int CHILD = 2 * x; CHILD <= 2 * x + 1; CHILD++) {
ckmax(tree[CHILD].s.s, tree[x].s.s); ckmax(tree[CHILD].s.f, tree[CHILD].s.s);
ckmin(tree[CHILD].s.f, tree[x].s.f); ckmin(tree[CHILD].s.s, tree[CHILD].s.f);
}
tree[x].s.f = INF; tree[x].s.s = 0;
}
void update(int x, int l, int r, int tl, int tr, int T, int H) { int mid = (l + r) / 2;
pushdown(x, l, r); if (l > tr || r < tl) return ; if (tl <= l && r <= tr) {
if (T == 1) { ckmax(tree[x].s.s, H); ckmax(tree[x].s.f, tree[x].s.s); }
if (T == 2) { ckmin(tree[x].s.f, H); ckmin(tree[x].s.s, tree[x].s.f); } return ;
}
update(2 * x, l, mid, tl, tr, T, H); update(2 * x + 1, mid + 1, r, tl, tr, T, H);
pushdown(2 * x, l, mid); pushdown(2 * x + 1, mid + 1, r); tree[x].f = max(tree[2 * x].f, tree[2 * x + 1].f);
}
void genAns(int x, int l, int r, int finalHeight[]) { int mid = (l + r) / 2;
pushdown(x, l, r); if (l == r) { finalHeight[l - 1] = tree[x].f; return ; }
genAns(2 * x, l, mid, finalHeight); genAns(2 * x + 1, mid + 1, r, finalHeight);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (int i = 1; i <= 4 * N; i++) { tree[i].s.f = INF; tree[i].s.s = 0; }
for (int i = 0; i < K; i++) update(1, 1, N, left[i] + 1, right[i] + 1, op[i], height[i]);
genAns(1, 1, N, finalHeight);
}
