/*
== ==
<^\()/^> <^\()/^>
\/ \/ \/ \/
/__\ . ' . /__\
== /\ . | . /\ ==
<^\()/^> !_\/ ' | ' \/_! <^\()/^>
\/ \/ !_/I_|| . ' \'/ ' . ||_I\_! \/ \/
/__\ /I_/| || -==C++==- || |\_I\ /__\
/_ \ !//| | || ' . /.\ . ' || | |\\! /_ \
(- ) /I/ | | || . | . || | | \I\ (= )
\__/!//| | | || ' | ' || | | |\\!\__/
/ \I/ | | | || ' . ' * || | | | \I/ \
{_ __} | | | || || | | | {____}
_!__|= || | | | || * + || | | | || |__!_
_I__| ||__|__|__|_|| A ||_|__|__|__||- |__I_
-|--|- ||--|--|--|-|| __/_\__ * ||-|--|--|--||= |--|-
| | || | | | || /\-'o'-/\ || | | | || | |
| |= || | | | || _||:<_>:||_ || | | | ||= | |
| |- || | | | || * /\_/=====\_/\ * || | | | ||= | |
| |- || | | | || __|:_:_[I]_:_:|__ || | | | ||- | |
_|__| ||__|__|__|_||:::::::::::::::::::::||_|__|__|__|| |__|_
-|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
jgs|- || | | | ||:::::::::::::::::::::|| | | | ||= | |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
struct SegTree {
std::vector<std::pair<int, int>> tree;
int sz;
const std::pair<int, int> identity = {0, INT_MAX};
SegTree(const int &n) {
sz = n;
tree = std::vector<std::pair<int, int>>(sz << 2 | 1, identity);
}
void apply(const int &id, const std::pair<int, int> &u) {
tree[id].ff = std::max(tree[id].ff, u.ff);
tree[id].ss = std::max(tree[id].ff, tree[id].ss);
tree[id].ss = std::min(tree[id].ss, u.ss);
tree[id].ff = std::min(tree[id].ss, tree[id].ff);
}
void push(const int &id) {
apply(id << 1, tree[id]);
apply(id << 1 | 1, tree[id]);
tree[id] = identity;
}
void upd(const int &id, const int &l, const int &r, const int &u,
const int &v, const std::pair<int, int> &t) {
if (l > v || r < u)
return;
if (l >= u && r <= v)
apply(id, t);
else {
push(id);
int m = (l + r) >> 1;
upd(id << 1, l, m, u, v, t);
upd(id << 1 | 1, m + 1, r, u, v, t);
}
}
void upd(const int &l, const int &r, const std::pair<int, int> &u) {
upd(1, 0, sz - 1, l, r, u);
}
std::pair<int, int> query(const int &id, const int &l, const int &r,
const int &p) {
if (l == r)
return tree[id];
push(id);
int m = (l + r) >> 1;
if (p <= m)
return query(id << 1, l, m, p);
return query(id << 1 | 1, m + 1, r, p);
}
std::pair<int, int> query(const int &l) { return query(1, 0, sz - 1, l); }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
SegTree st(n);
for (int i = 0; i < k; i++) {
if (op[i] == 1)
st.upd(left[i], right[i], {height[i], INT_MAX});
else
st.upd(left[i], right[i], {0, height[i]});
}
for (int i = 0; i < n; i++) {
finalHeight[i] = st.query(i).ff;
// std::cout << finalHeight[i] << ' ';
}
}
// int main() {
// std::ios_base::sync_with_stdio(false);
// std::cin.tie(0);
// std::cout.tie(0);
// int n, k;
// std::cin >> n >> k;
// int op[n], left[n], right[n], height[n];
// int finalHeight[n];
// for (int i = 0; i < n; i++)
// std::cin >> op[i] >> left[i] >> right[i] >> height[i];
// buildWall(n, k, op, left, right, height, finalHeight);
// }
