/**
* 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;
const int N = 4e6+2e5;
struct segtree {
pair<int, int> tree[N];
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(1, 2*x+1, lo);
push(2, 2*x+1, hi);
push(1, 2*x+2, lo);
push(2, 2*x+2, hi);
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;
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);
}
