#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
const int INF = 1e9 + 7;
class Block {
public :
int low, high;
Block() : low(0), high(INF) {}
};
class SegmentTree {
protected :
const int N;
vector <Block> tree;
public :
SegmentTree(const int &n) : N(n) {
tree.resize(4 * n, Block());
}
void push(const int &idx, const int &l, const int &r) {
if(l == r) {
return;
}
push_lazy(idx * 2, 1, tree[idx].low);
push_lazy(idx * 2, 2, tree[idx].high);
push_lazy(idx * 2 + 1, 1, tree[idx].low);
push_lazy(idx * 2 + 1, 2, tree[idx].high);
tree[idx] = Block();
}
void push_lazy(int idx, const int &op, const int &h) {
if(op == 1) {
tree[idx].low = max(tree[idx].low, h);
tree[idx].high = max(tree[idx].high, tree[idx].low);
}
else {
tree[idx].high = min(tree[idx].high, h);
tree[idx].low = min(tree[idx].low, tree[idx].high);
}
}
void update(const int &idx, const int &l, const int &r, const int &ql, const int &qr, const int &op, const int &h) {
if(r < ql or qr < l) {
return;
}
if(ql <= l and r <= qr) {
push_lazy(idx, op, h);
return;
}
push(idx, l, r);
int mid = (l + r) / 2;
update(idx * 2, l, mid, ql, qr, op, h);
update(idx * 2 + 1, mid + 1, r, ql, qr, op, h);
}
void answer(const int &idx, const int &l, const int &r, int arr[]) {
if(l == r) {
arr[l] = tree[idx].low;
return;
}
push(idx, l, r);
int mid = (l + r) / 2;
answer(idx * 2, l, mid, arr);
answer(idx * 2 + 1, mid + 1, r, arr);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegmentTree st(n);
for(int i = 0; i < k; i++) {
st.update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
}
st.answer(1, 0, n - 1, finalHeight);
}
