#include "wall.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
using S = P;
const S e = {0, inf};
constexpr S op(const S &l, const S &r) {
if (l.second <= r.first) return {r.first, r.first};
if (r.second <= l.first) return {r.second, r.second};
return {max(l.first, r.first), min(l.second, r.second)};
}
class dual_segtree {
int n, log;
vector<S> d;
void all_apply(int p, const S &x) {
d[p] = op(d[p], x);
}
void push(int p) {
all_apply(2 * p, d[p]);
all_apply(2 * p + 1, d[p]);
d[p] = e;
}
public:
dual_segtree(int _n) {
log = 1;
while (1 << log < _n) ++log;
n = 1 << log;
d.assign(2 * n, e);
}
void apply(int l, int r, const S &x) {
assert(0 <= l and l <= r and r <= n);
l += n, r += n;
rrep2(i, log + 1, 1) {
if (l >> i << i != l) push(l >> i);
if (r >> i << i != r) push(r >> i);
}
while (l < r) {
if (l & 1) all_apply(l++, x);
if (r & 1) all_apply(--r, x);
l >>= 1, r >>= 1;
}
}
vector<S> all_get() {
rep2(i, 1, n) push(i);
return vector<S>(d.begin() + n, d.end());
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
dual_segtree st(n);
rep(i, k) {
++right[i];
if (op[i] == 1) st.apply(left[i], right[i], {height[i], inf});
else st.apply(left[i], right[i], {0, height[i]});
}
auto ans = st.all_get();
rep(i, n) finalHeight[i] = ans[i].first;
}
