#include "wall.h"
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 2;
struct st{
int a, b, x;
st(){
a = b = 0;
}
}t[N * 4];
int nn;
void push(int v, int tl, int tr){
int tm = (tl + tr) >> 1;
if(t[v].b == 1){
t[v].a = max(t[v].a, t[v].x);
if(tl != tr){
if(t[v << 1].b)
push(v << 1, tl, tm);
if(t[(v << 1) | 1].b)
push((v << 1) | 1, tm + 1, tr);
t[v << 1].b = t[(v << 1) | 1].b = 1;
t[v << 1].x = t[(v << 1) | 1].x = t[v].x;
}
}
if(t[v].b == 2){
t[v].a = min(t[v].a, t[v].x);
if(tl != tr){
if(t[v << 1].b)
push(v << 1, tl, tm);
if(t[(v << 1) | 1].b)
push((v << 1) | 1, tm + 1, tr);
t[v << 1].b = t[(v << 1) | 1].b = 2;
t[v << 1].x = t[(v << 1) | 1].x = t[v].x;
}
}
t[v].b = 0;
}
void update(int l, int r, int x, int op, int v = 1, int tl = 1, int tr = nn){
push(v, tl, tr);
if(l > tr || tl > r) return ;
if(l <= tl && tr <= r){
t[v].x = x;
t[v].b = op;
push(v, tl, tr);
return ;
}
int tm = (tl + tr) >> 1;
update(l, r, x, op, v << 1, tl, tm);
update(l, r, x, op, (v << 1) | 1, tm + 1, tr);
}
int get(int pos, int v = 1, int tl = 1, int tr = nn){
push(v, tl, tr);
if(tl == tr)
return t[v].a;
int tm = (tl + tr) >> 1;
if(pos <= tm)
return get(pos, v << 1, tl, tm);
return get(pos, (v << 1) | 1, tm + 1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
nn = n;
for(int i = 0; i < k; i ++){
update(left[i] + 1, right[i] + 1, height[i], op[i]);
}
for(int i = 0; i < n; i ++){
finalHeight[i] = get(i + 1);
}
}
