#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N=(1<<21); //sprawdzic
pair<int, int> tree[2*N+7]; //lower, upper
void Push(int w){
tree[2*w].F=max(tree[2*w].F, tree[w].F);
tree[2*w].S=min(tree[2*w].S, tree[w].S);
tree[2*w+1].F=max(tree[2*w+1].F, tree[w].F);
tree[2*w+1].S=min(tree[2*w+1].S, tree[w].S);
}
void Update(int w, int b, int e, int l, int r, int h, bool num){
if (l>e || r<b) return;
if (l>=b && r<=e){
if (num) {
tree[w].F=max(tree[w].F, h);
tree[w].S=max(tree[w].S, h);
}
else {
tree[w].F=min(tree[w].F, h);
tree[w].S=min(tree[w].S, h);
}
}
if (w<N) Push(w);
Update(2*w, b, e, l, (l+r)/2, h, num);
Update(2*w+1, b, e, (l+r)/2, r, h, num);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fill(tree, tree+2*N, make_pair(0, 1e9));
for (int i=0; i<k; i++) Update(1, left[i], right[i], 0, N-1, height[i], op[i]-1);
for (int i=1; i<N; i++) Push(i);
generate(finalHeight, finalHeight+n, [&, i=0] mutable{
return finalHeight[i]=tree[i++].F;
});
}
