#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e6 + 7;
const ll oo = 1e9 + 69;
int n, k, op[maxn], l[maxn], r[maxn], height[maxn], ans[maxn];
struct ST {
struct node {
int val;
};
node st[4 * maxn];
pa lz[4 * maxn];
void init() {
for(int id = 1; id <= 4 * n; id++) {
st[id].val = 0;
lz[id] = {-oo, oo};
}
}
void fix(int id, int l, int r, int type) {
if(type == 1) {
maxi(st[id].val, lz[id].fi);
} else {
mini(st[id].val, lz[id].se);
}
if(l != r) {
if(type == 1) {
maxi(lz[id << 1].fi, lz[id].fi);
maxi(lz[id << 1].se, lz[id].fi);
maxi(lz[id << 1 | 1].fi, lz[id].fi);
maxi(lz[id << 1 | 1].se, lz[id].fi);
} else {
mini(lz[id << 1].fi, lz[id].se);
mini(lz[id << 1].se, lz[id].se);
mini(lz[id << 1 | 1].fi, lz[id].se);
mini(lz[id << 1 | 1].se, lz[id].se);
}
}
if(type == 1) lz[id].fi = -oo;
else lz[id].se = oo;
}
void update(int id, int l, int r, int u, int v, int val, int type) {
fix(id, l, r, 0);
fix(id, l, r, 1);
if(r < u || l > v) return;
if(u <= l && r <= v) {
if(type == 1) {
maxi(lz[id].fi, val);
maxi(lz[id].se, val);
} else {
mini(lz[id].fi, val);
mini(lz[id].se, val);
}
fix(id, l, r, type);
return;
}
int mid = l + r >> 1;
update(id << 1, l, mid, u, v, val, type);
update(id << 1 | 1, mid + 1, r, u, v, val, type);
}
void get(int id, int l, int r) {
fix(id, l, r, 0);
fix(id, l, r, 1);
if(l == r) {
ans[l] = st[id].val;
return;
}
int mid = l + r >> 1;
get(id << 1, l, mid);
get(id << 1 | 1, mid + 1, r);
}
} st;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
st.init();
for(int i = 0; i < k; i++) {
st.update(1, 1, n, left[i] + 1, right[i] + 1, height[i], op[i]);
}
st.get(1, 1, n);
for(int i = 0; i < n; i++) {
finalHeight[i] = ans[i + 1];
}
}
