#include <bits/stdc++.h>
using namespace std;
struct SegmentTree{
struct Node{
int mx, mn;
};
vector<Node> tree;
vector<bool> lazy;
int sz = 1;
SegmentTree(int n){
while(sz < n)
sz <<= 1;
tree.resize(2*sz);
lazy.resize(2*sz);
}
Node merge(Node x, Node c){
if(x.mn >= c.mx) return {x.mn, x.mn};
if(x.mx <= c.mn) return {x.mx, x.mx};
return {min(x.mx, c.mx), max(x.mn, c.mn)};
}
inline int lc(int x) { return 2*x+1; }
inline int rc(int x) { return 2*x+2; }
void push(int x){
lazy[x] = 0;
lazy[lc(x)] = lazy[rc(x)] = 1;
tree[lc(x)] = merge(tree[x], tree[lc(x)]);
tree[rc(x)] = merge(tree[x], tree[rc(x)]);
tree[x] = {1000000, 0};
}
void update(int l, int r, int t, int val, int x, int lx, int rx){
if(rx <= l || lx >= r)
return;
if(lx >= l && rx <= r){
lazy[x] = 1;
if(t == 0) tree[x] = {max(tree[x].mx, val), max(tree[x].mn, val)};
else tree[x] = {min(tree[x].mx, val), min(tree[x].mn, val)};
return;
}
int mid = (lx + rx) >> 1;
if(lazy[x]) push(x);
update(l, r, t, val, lc(x), lx, mid);
update(l, r, t, val, rc(x), mid, rx);
}
void construct(int x, int lx, int rx, int ans[]){
if(rx - lx == 1){
ans[lx] = 0;
ans[lx] = min(ans[lx], tree[x].mx);
ans[lx] = max(ans[lx], tree[x].mn);
return;
}
int mid = (lx + rx) >> 1;
if(lazy[x])
push(x);
construct(lc(x), lx, mid, ans);
construct(rc(x), mid, rx, ans);
}
void update(int l, int r, int t, int val) { update(l, r, t, val, 0, 0, sz); }
void construct(int ans[]){ construct(0, 0, sz, ans); }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegmentTree S(n);
for(int i = 0; i < k; i++)
S.update(left[i], right[i] + 1, op[i] - 1, height[i]);
S.construct(finalHeight);
}
