#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 st[4 * N], lzy[4 * N], tg[4 * N];
void Propagate(int node, int l, int r) {
if (tg[node] == 0) return;
if (l < r) {
tg[2 * node] = tg[2 * node + 1] = tg[node];
lzy[2 * node] = lzy[2 * node + 1] = lzy[node];
}
if (tg[node] == 1) smax(st[node], lzy[node]);
if (tg[node] == 2) smin(st[node], lzy[node]);
tg[node] = lzy[node] = 0;
}
void Change(int node, int l, int r, int ql, int qr, int o, int x) {
Propagate(node, l, r);
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
lzy[node] = x;
tg[node] = o;
Propagate(node, l, r);
return;
}
int mid = l + r >> 1;
Change(2 * node, l, mid, ql, qr, o, x);
Change(2 * node + 1, mid + 1, r, ql, qr, o, x);
st[node] = max(st[2 * node], st[2 * node + 1]);
}
vector<int> v;
void Walk(int node, int l, int r) {
Propagate(node, l, r);
if (l == r) {v.push_back(st[node]); return; }
int mid = l + r >> 1;
Walk(2 * node, l, mid);
Walk(2 * node + 1, mid + 1, r);
st[node] = max(st[2 * node], st[2 * node + 1]);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[]) {
for (int i = 0; i < q; i++) Change(1, 0, n - 1, l[i], r[i], op[i], h[i]);
Walk(1, 0, n - 1);
for (int i = 0; i < n; i++) ans[i] = v[i];
}
