#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
struct SeggsTree{
SeggsTree *l = 0, *r = 0;
int low = 0, high = 0;
struct Data{
ll mx, mn;
Data() {mx = -(INT_MAX-1), mn = INT_MAX;}
Data(ll X, ll N) {mx = X, mn = N;}
void update(ll k){
mx = k, mn = k;
}
static Data merge(Data a, Data b){
return Data(max(a.mx, b.mx), min(a.mn, b.mn));
}
};
Data d;
SeggsTree(int L, int R){
low = L, high = R;
if(R - L <= 1){
d = Data(0, 0);
return;
}
int mid = low + (high - low) / 2;
l = new SeggsTree(low, mid);
r = new SeggsTree(mid, high);
}
~SeggsTree(){
if(!l) return;
delete l;
delete r;
}
bool lazy = false;
void push(){
if(!l) return;
if(!lazy) return;
l->d.mn = d.mn;
l->d.mx = d.mx;
l->lazy = true;
r->d.mn = d.mn;
r->d.mx = d.mx;
r->lazy = true;
lazy = false;
}
Data query(int L, int R){
if(R <= low || high <= L) return Data();
if(L <= low && high <= R) return d;
push();
return Data::merge(l->query(L,R), r->query(L, R));
}
void updateAdd(int L, int R, ll k){
if(R <= low || high <= L || d.mn >= k) return;
if(L <= low && high <= R && d.mx == d.mn){
d.update(max(d.mx, k));
lazy = true;
return;
}
push();
l->updateAdd(L, R, k);
r->updateAdd(L, R, k);
d = Data::merge(l->d, r->d);
}
void updateSub(int L, int R, ll k){
if(R <= low || high <= L || d.mx <= k) return;
if(L <= low && high <= R && d.mn >= k){
d.update(min(d.mx, k));
lazy = true;
return;
}
push();
l->updateSub(L, R, k);
r->updateSub(L, R, k);
d = Data::merge(l->d, r->d);
}
};
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]){
SeggsTree *tree = new SeggsTree(0, n);
for(int i = 0; i < k; i++){
if(op[i] == 1) tree->updateAdd(left[i], right[i]+1, height[i]);
else tree->updateSub(left[i], right[i]+1, height[i]);
}
for(int i = 0; i < n; i++) finalHeight[i] = tree->query(i, i+1).mn;
}
int main(){
}
