#include "wall.h"
#include <bits/stdc++.h>
namespace {
const int N = 2e6 + 5, inf = 1e9;
int n;
std::array<int, 2> s[4 * N];
void bld(int id = 1, int l = 0, int r = n - 1) {
if (l == r) {
s[id] = {0, 0};
return;
}
s[id] = {-inf, inf};
int md = (l + r) / 2;
bld(id * 2, l, md);
bld(id * 2 + 1, md + 1, r);
}
void app(int id, int x, int op) {
for (auto it : {0, 1}) {
if (op == 2) {
s[id][it] = std::min(s[id][it], x);
} else {
s[id][it] = std::max(s[id][it], x);
}
}
}
void psh(int id) {
if (s[id] != std::array<int, 2>{inf, -inf}) {
for (auto i : {id * 2, id * 2 + 1}) {
app(i, s[id][0], 1);
app(i, s[id][1], 2);
}
s[id] = {-inf, inf};
}
}
void upd(int u, int v, int x, int op, int id = 1, int l = 0, int r = n - 1) {
if (u <= l && r <= v) {
app(id, x, op);
return;
}
psh(id);
int md = (l + r) / 2;
if (u <= md) {
upd(u, v, x, op, id * 2, l, md);
}
if (md < v) {
upd(u, v, x, op, id * 2 + 1, md + 1, r);
}
}
int qry(int i, int id = 1, int l = 0, int r = n - 1) {
if (l == r) {
assert(s[id][0] == s[id][1]);
return s[id][0];
}
psh(id);
int md = (l + r) / 2;
return i <= md ? qry(i, id * 2, l, md) : qry(i, id * 2 + 1, md + 1, r);
}
}
void buildWall(int n, int k, int *op, int *le, int *ri, int *a, int *res) {
::n = n;
bld();
for (int i = 0; i < k; ++i) {
upd(le[i], ri[i], a[i], op[i]);
}
for (int i = 0; i < n; ++i) {
res[i] = qry(i);
}
}
