/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//const ll inf = 1e18;
int* res;
struct segtree {
vector<pair<int, int>> tree;
void init(int n) {
int size = 1;
while (size < n)size <<= 1;
tree.assign(2*size-1, {0, 0});
}
void push(int x, int val, int op) {
int &l = tree[x].first, &r = tree[x].second;
l = (op == 1?max(l, val):min(l, val));
r = (op == 1?max(r, val):min(r, val));
}
void apply(int l, int r, int val, int op, int x, int lx, int rx) {
if (rx <= l || r <= lx)return;
if (lx >= l && rx <= r) {
push(x, val, op);
res[l] = tree[x].first;
return;
}
int &lo = tree[x].first, &hi = tree[x].second;
push(2*x+1, lo, 1);
push(2*x+1, hi, 2);
push(2*x+2, lo, 1);
push(2*x+2, hi, 2);
lo = 0, hi = 1e5+5;
int m = lx+rx>>1;
apply(l, r, val, op, 2*x+1, lx, m);
apply(l, r, val, op, 2*x+2, m, rx);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
segtree a;
a.init(n);
res = finalHeight;
for (int i = 0; i < k; ++i)
a.apply(left[i], right[i]+1, height[i], op[i], 0, 0, n);
for (int i = 0; i < n; ++i)
a.apply(i, i+1, 0, 1, 0, 0, n);
}
