#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef ENABLE_DEBUG
#include <debug.h>
#else
#define DEBUG(...) do {} while (0)
#endif
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;
using ld = long double;
template<typename T, size_t N> using ar = array<T, N>;
template<typename T, typename Cmp = less<T>>
using iset = tree<T, null_type, Cmp, rb_tree_tag,
tree_order_statistics_node_update, allocator<T>>;
#define REPSI(name, start, stop, step) for (ll name = start; name < (ll)stop; name += step)
#define REPS(name, start, stop) REPSI(name, start, stop, 1)
#define REP(name, stop) REPS(name, 0, stop)
#define RREPSI(name, start, stop, step) for (ll name = stop-1; name >= (ll)start; name -= step)
#define RREPS(name, start, stop) RREPSI(name, start, stop, 1)
#define RREP(name, stop) RREPS(name, 0, stop)
template<typename T> void cins(T &first) { cin >> first; }
template<typename T, typename... Ts> void cins(T &first, T &second, Ts&... rest) {
cin >> first;
cins(second, rest...);
}
#define GET(type, ...) type __VA_ARGS__; cins(__VA_ARGS__)
#define GETI(...) GET(int, __VA_ARGS__)
#define GETLL(...) GET(ll, __VA_ARGS__)
#define GETS(...) GET(string, __VA_ARGS__)
#define GETD(...) GET(double, __VA_ARGS__)
#define GETC(...) GET(char, __VA_ARGS__)
struct hsh {
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
x += FIXED_RANDOM;
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
};
template<class S, class F>
struct SegTreeBase {
vector<S> values;
vector<F> queued;
int lg2, offset;
static constexpr int log2i(unsigned n) { return 32-__builtin_clz(--n); }
SegTreeBase(const vector<S> &src)
: lg2(log2i((int)src.size())), offset(1<<log2i((int)src.size())) {
values.reserve(2*offset);
values.resize(offset);
values.insert(values.end(), src.begin(), src.end());
values.resize(2*offset);
queued.resize(offset);
for (int i = offset-1; i > 0; --i) recalc(i);
}
void recalc(int I) {
assert(I > 0 && I < offset);
values[I] = values[2*I] * values[2*I+1];
}
void push(int I) {
assert(I > 0 && I < offset);
values[2*I] = queued[I] * values[2*I];
values[2*I+1] = queued[I] * values[2*I+1];
if (2*I < offset) {
queued[2*I] = queued[I] * queued[2*I];
queued[2*I+1] = queued[I] * queued[2*I+1];
}
queued[I] = F();
}
void push_col(int I) {
assert(I >= offset && I < 2*offset);
for (int lvl = lg2-1; lvl >= 0; --lvl)
push((I>>lvl)/2);
}
void push_range(int I, int J) {
assert(I+1 >= offset && I+1 < 2*offset);
assert(J-1 >= offset && J-1 < 2*offset);
assert(I+1 < J);
for (int lvl = lg2-1; lvl >= 0; --lvl) {
push(((I+1)>>lvl)/2);
if (I+1 != J-1) push(((J-1)>>lvl)/2);
}
}
void set(int i, S v) {
assert(i >= 0 && i < offset);
i += offset;
push_col(i);
values[i] = v;
while (i /= 2) recalc(i);
}
void upd_node(int I, const F &f) {
assert(I > 0 && I < 2*offset);
values[I] = f * values[I];
if (I < offset) queued[I] = f * queued[I];
}
void upd(int i, const F &f) {
assert(i >= 0 && i < offset);
i += offset;
push_col(i);
upd_node(i, f);
while (i/=2) recalc(i);
}
void upd(int i, int j, const F &f) {
assert(i >= 0 && i < offset);
assert(j >= 0 && j < offset);
assert(i <= j);
i += offset-1;
j += offset+1;
int oi = i, oj = j;
push_range(i, j);
while (i+1 < j) {
if ((i&1)==0) upd_node(i+1, f);
if ((j&1)==1) upd_node(j-1, f);
i >>= 1, j >>= 1;
}
i = oi+1, j = oj-1;
for (int lvl = 1; lvl <= lg2; lvl++) {
if (__builtin_ctz(i) < lvl) recalc(i >> lvl);
if (__builtin_ctz(j+1) < lvl) recalc(j >> lvl);
}
}
S qry(int i) {
assert(i >= 0 && i < offset);
i += offset;
push_col(i);
return values[i];
}
S qry(int i, int j) {
assert(i >= 0 && i < offset);
assert(j >= 0 && j < offset);
assert(i <= j);
i += offset-1;
j += offset+1;
push_range(i, j);
S ls, rs;
while (i+1 < j) {
if ((i&1)==0) ls = ls * values[i+1];
if ((j&1)==1) rs = values[j-1] * rs;
i >>= 1, j >>= 1;
}
return ls * rs;
}
template<class Cmp>
int upper_bound(S t, Cmp cmp) {
if (cmp(values[1], t)) return offset;
int lvl = lg2;
int I = 1;
S pre;
while (lvl--) {
I *= 2;
push(I/2);
if (cmp(pre*values[I], t)) {
pre = pre*values[I];
++I;
}
}
return I - offset;
}
};
struct S {
ll v = 0;
S operator*(const S &rhs) const { return *this; }
};
const ll INF = 1LL<<60;
struct F {
ll mn = INF;
ll mx = -INF;
F operator*(const F &rhs) const {
F ret = rhs;
ret.mn = min(ret.mn, mn);
ret.mx = min(ret.mx, mn);
ret.mn = max(ret.mn, mx);
ret.mx = max(ret.mx, mx);
assert(ret.mn >= ret.mx);
return ret;
}
S operator*(const S &rhs) const {
return {min(max(rhs.v, mx), mn)};
}
};
using SegTree = SegTreeBase<S, F>;
void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]) {
vector<S> src(n);
SegTree st(src);
REP(qq, q) {
int i = left[qq];
int j = right[qq];
int h = height[qq];
if (op[qq] == 1) {
st.upd(i, j, {INF, h});
} else if (op[qq] == 2) {
st.upd(i, j, {h, -INF});
} else assert(false);
}
REPS(I, 1, st.offset) st.push(I);
REP(i, n) finalHeight[i] = st.values[st.offset+i].v;
}
