#include <bits/stdc++.h>
using namespace std;
typedef 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) {
for (int CHILD = 2 * x; CHILD <= 2 * x + 1; CHILD++) {
ckmax(tree[CHILD].s, tree[x].s); ckmax(tree[CHILD].f, tree[CHILD].s);
ckmin(tree[CHILD].f, tree[x].f); ckmin(tree[CHILD].s, tree[CHILD].f);
}
}
void update(int x, int l, int r, int tl, int tr, int T, int H) { int mid = (l + r) / 2;
if (l > tr || r < tl) return ; if (tl <= l && r <= tr) {
if (T == 1) { ckmax(tree[x].s, H); ckmax(tree[x].f, tree[x].s); return ; }
if (T == 2) { ckmin(tree[x].f, H); ckmin(tree[x].s, tree[x].f); return ; }
}
pushdown(x, l, r); update(2 * x, l, mid, tl, tr, T, H); update(2 * x + 1, mid + 1, r, tl, tr, T, H);
}
void genAns(int x, int l, int r, int finalHeight[]) { int mid = (l + r) / 2;
if (l == r) { finalHeight[l - 1] = tree[x].s; return ; }
pushdown(x, l, r); 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].f = INF; tree[i].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);
}
