#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N=(1<<20); //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);
}
}
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+1, 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);
copy(tree+N, tree+N+n, finalHeight);
}
