#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 5e5+100;
const ll INF = 1e9;
ll n,k;
namespace segtree{
pll tree[MAXN*4];
void build(ll id,ll l,ll r){
tree[id] = MP(0,INF);
if (l != r){
ll mid = (l + r) >> 1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
}
}
void update(ll id,ll l,ll r,ll i,pll v){
if (l > i || r < i)return;
if (l==r){
tree[id] = v;
return;
}
ll mid = (l + r) >> 1;
update(id<<1,l,mid,i,v);
update(id<<1|1,mid+1,r,i,v);
if (tree[id<<1].fi > tree[id<<1|1].se){
tree[id] = MP(tree[id<<1|1].se,tree[id<<1|1].se);
}
else if (tree[id<<1|1].fi > tree[id<<1].se){
tree[id] = MP(tree[id<<1|1].fi,tree[id<<1|1].fi);
}
else{
tree[id].fi = max(tree[id<<1].fi,tree[id<<1|1].fi);
tree[id].se = min(tree[id<<1].se,tree[id<<1|1].se);
}
// cout<<"SUS "<<id<<' '<<l<<' '<<r<<' '<<tree[id].fi<<' '<<tree[id].se<<'\n';
}
void update(ll i,pll v){
// cout<<i<<' '<<v.fi<<' '<<v.se<<'\n';
update(1,1,k,i,v);
}
}
struct query{
ll time,type,h,x,ins;
};
vector <query> all;
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
n=N,k=K;
for (ll i = 0;i < k;i ++){
all.push_back({i+1,op[i],height[i],left[i],true});
all.push_back({i+1,op[i],height[i],right[i]+1,false});
}
sort(all.begin(),all.end(),[&](query a,query b){return a.x < b.x;});
// cout<<"SUS "<<all[0].x<<endl;
using namespace segtree;
build(1,1,k);
for (ll i = 0,ptr = 0;i < n;i ++){
while (ptr<sz(all) && all[ptr].x==i){
query tmp = all[ptr];
if (tmp.ins){
pll rg;
if (tmp.type==1)rg = MP(tmp.h,INF);
else rg = MP(0,tmp.h);
update(tmp.time,rg);
}
else{
update(tmp.time,MP(0,INF));
}
ptr++;
}
// cout<<i<<' '<<tree[1].fi<<'\n';
finalHeight[i] = tree[1].fi;
}
return;
}
