#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXA = 1e6;
vector<pair<int, int>> st;
vector<pair<int, int>> lp;
void findNewVal(pair<int, int> &l, pair<int, int> &r) {
l.f = max(l.f, min(r.f, l.s));
l.s = min(l.s, max(r.s, l.f));
}
void updateLazy(int curr, bool leaf, int pos) {
if (leaf) {
findNewVal(st[pos], lp[curr]);
return;
}
findNewVal(lp[curr*2], lp[curr]);
findNewVal(lp[curr*2+1], lp[curr]);
lp[curr] = {0, MAXA};
}
void update(int curr, int l, int r, int b, int e, int val, int type) {
updateLazy(curr, l==r, l);
if (l > e || r < b) {
return;
}
if (l >= b && r <= e) {
if (type == 1) {
lp[curr].f = min(lp[curr].s, val);
} else if (type == 2) {
lp[curr].s = max(lp[curr].f, val);
}
return;
}
int mid = (l+r)/2;
update(curr*2, l, mid, b, e, val, type);
update(curr*2+1, mid+1, r, b, e, val, type);
}
void calcAns(int curr, int l, int r) {
//cerr<<l<<' '<<r<<" - "<<lp[curr].f<<' '<<lp[curr].s<<endl;
updateLazy(curr, l==r, l);
if (l == r) {
return;
}
int mid = (l+r)/2;
calcAns(curr*2, l, mid);
calcAns(curr*2+1, mid+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
st.resize(n, {0, MAXA}), lp.resize(4*n, {0, MAXA});
for (int i=k-1; i>=0; i--) {
update(1, 0, n-1, left[i], right[i], height[i], op[i]);
}
calcAns(1, 0, n-1);
for (int i=0; i<n; i++) {
finalHeight[i] = st[i].f;
}
return;
}
