#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e6 + 2;
int mx[4 * N], mn[4 * N], lzymn[4 * N], lzymx[4 * N], sol[N];
void Propagate(int node, int l, int r) {
if (lzymn[node] != 1e9) {
if (mn[node] != 1e9) smin(mn[node], lzymn[node]);
if (l < r) {
smin(lzymn[2 * node], lzymn[node]);
smin(lzymn[2 * node + 1], lzymn[node]);
}
lzymn[node] = 1e9;
}
if (lzymx[node] != -1e9) {
if (mx[node] != -1e9) smax(mx[node], lzymx[node]);
if (l < r) {
smax(lzymx[2 * node], lzymx[node]);
smax(lzymx[2 * node + 1], lzymx[node]);
}
lzymx[node] = -1e9;
}
}
void Walk(int node, int l, int r, int val, int op) {
Propagate(node, l, r);
if (op == 1 && val <= mn[node]) return;
if (op == 2 && mx[node] <= val) return;
if (l == r) {
if (op == 1) sol[l] = mn[node];
else sol[l] = mx[node];
mx[node] = -1e9;
mn[node] = 1e9;
return;
}
int mid = l + r >> 1;
Walk(2 * node, l, mid, val, op);
Walk(2 * node + 1, mid + 1, r, val, op);
mn[node] = min(mn[2 * node], mn[2 * node + 1]);
mx[node] = max(mx[2 * node], mx[2 * node + 1]);
}
void Update(int node, int l, int r, int ql, int qr, int op, int val) {
Propagate(node, l, r);
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
if (op == 1) smax(lzymx[node], val);
else smin(lzymn[node], val);
Propagate(node, l, r);
if (mx[node] <= mn[node]) return;
Walk(node, l, r, val, op);
return;
}
int mid = l + r >> 1;
Update(2 * node, l, mid, ql, qr, op, val);
Update(2 * node + 1, mid + 1, r, ql, qr, op, val);
mn[node] = min(mn[2 * node], mn[2 * node + 1]);
mx[node] = max(mx[2 * node], mx[2 * node + 1]);
}
void FindAnswer(int node, int l, int r) {
Propagate(node, l, r);
if (l == r) {
if (sol[l] == -1) sol[l] = mx[node];
return;
}
int mid = l + r >> 1;
FindAnswer(2 * node, l, mid);
FindAnswer(2 * node + 1, mid + 1, r);
mn[node] = min(mn[2 * node], mn[2 * node + 1]);
mx[node] = max(mx[2 * node], mx[2 * node + 1]);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[]) {
for (int i = 0; i < n; i++) sol[i] = -1;
for (int i = 1; i <= 4 * n; i++) {
mx[i] = 0; mn[i] = 1e5;
lzymx[i] = -1e9; lzymn[i] = 1e9;
}
for (int i = q - 1; i >= 0; i--) {
Update(1, 0, n - 1, l[i], r[i], op[i], h[i]);
}
FindAnswer(1, 0, n - 1);
for (int i = 0; i < n; i++) {
ans[i] = sol[i];
}
}
