#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
pii seg[8000010];
pii nil={-1, -1};
void build(int v, int tl, int tr){
if(tl==tr){
seg[v]=nil;
return;
}
int mid=(tl+tr)>>1ll;
build(v*2, tl, mid); build(2*v+1, mid+1, tr);
}
void lazy(pii &sus, pii &jos){
if(sus==nil){return;}
if(jos==nil){jos={sus.ft, sus.sc}; sus=nil; return;}
int hs=sus.ft, rs=sus.sc, hj=jos.ft, rj=jos.sc;
if(rs<hj){
jos={max(rs, hs), min(rs, rj)};
}
else{
jos={max(hj, hs), min(rs, rj)};
}
sus=nil;
return;
}
void update(int v, int tl, int tr, int l, int r, int tp, int x){
if(l>r){return;}
if( (tl==l) && (tr==r) ){
pii p={0, 0};
if(tp==1){
p.ft=x; p.sc=100000;
}
else{
p.sc=x;
}
lazy(p, seg[v]);
return;
}
pii p={seg[v].ft, seg[v].sc};
lazy(seg[v], seg[v*2]), lazy(p, seg[v*2+1]);
int mid=(tl+tr)>>1ll;
update(2*v, tl, mid, l, min(r, mid), tp, x); update(2*v+1, mid+1,tr, max(l, mid+1),r, tp, x);
return;
}
int query(int v, int tl, int tr, int p){
int mid=(tl+tr)>>1ll;
if(tl==tr){
return seg[v].ft;
}
pii pr={seg[v].ft, seg[v].sc};
lazy(seg[v], seg[v*2]), lazy(pr, seg[v*2+1]);
if(p<=mid){
return query(2*v, tl, mid, p);
}
else{
return query(2*v+1, mid+1, tr, p);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1, 1, n);
for(int i=0; i<k; i++){
update(1, 1, n, left[i]+1, right[i]+1, op[i], height[i]);
}
for(int i=0; i<n; i++){
finalHeight[i]=query(1, 1, n,i+1);
}
return;
}
