#include <iostream>
using namespace std;
const int inf = 1e9, N = 1 << 22;
int mx[N], mn[N];
void change(int v, int d, int u) {
mn[v] = max(u, min(d, mn[v]));
mx[v] = min(d, max(u, mx[v]));
}
void push(int v) {
change(v << 1|0, mn[v], mx[v]);
change(v << 1|1, mn[v], mx[v]);
mx[v] = 0; mn[v] = inf;
}
int d, u, lo, hi;
void update(int v, int l, int r) {
if (hi <= l || r <= lo) return;
if (lo <= l && r <= hi) return change(v, d, u);
push(v); int m = (l + r) / 2;
update(v << 1|0, l, m);
update(v << 1|1, m, r);
}
void final(int ans[], int v, int l, int r) {
if (r - l == 1)
return void(ans[l] = min(mx[v], mn[v]));
push(v); int m = (l + r) / 2;
final(ans, v << 1|0, l, m);
final(ans, v << 1|1, m, r);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[]) {
for (int i = 0; i < N; ++i) mn[i] = inf, mx[i] = 0;
for (int i = 0; i < q; ++i) {
u = 0; d = inf;
lo = l[i]; hi = r[i] + 1;
op[i] != 1 ? d = h[i]: u = h[i];
update(1, 0, n);
}
final(ans, 1, 0, n);
}
