#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#include "wall.h"
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
pair<int,int>tree[8000010];
void build(int node,int l,int r){
if(l==r){
tree[node]=mp(-1,-1);
return;
}
int mid=(l+r)/2;
build(2*node,l,mid);
build(2*node,mid+1,r);
}
void add(pair<int,int> &s,pair<int,int> &j){
if(s==mp(-1,-1)){
return;
}
if(j==mp(-1,-1)){
j=mp(s.f,s.s);
s=mp(-1,-1);
return;
}
int a,b,c,d;
a=s.f;
b=s.s;
c=j.f;
d=j.s;
if(b<c){
j=mp(max(a,b),min(b,d));
}else {
j=mp(max(a,c),min(c,d));
}
s=mp(-1,-1);
return;
}
void update(int node,int l,int r,int st,int dr,int type,int h){
if(st>dr){
return;
}
if(l==st&&r==dr){
pair<int,int>p={0,0};
if(type==1){
p.f=h;
p.s=100000;
}else {
p.s=h;
}
add(p,tree[node]);
return;
}
pair<int,int>p=tree[node];
add(tree[node],tree[node*2]);
add(p,tree[node*2+1]);
int mid=(l+r)>>1ll;
update(2*node,l,mid,st,min(dr,mid),type,h);
update(2*node+1,mid+1,r,max(st,mid+1),dr,type,h);
return;
}
int query(int node,int l,int r,int pos){
if(l==r){
return tree[node].f;
}
pair<int,int>p=tree[node];
add(tree[node],tree[node*2]);
add(p,tree[node*2+1]);
int mid=(l+r)>>1ll;
if(pos<=mid){
return query(2*node,l,mid,pos);
}else return query(2*node+1,mid+1,r,pos);
}
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;
}
/*
int32_t main(){
CODE_START;
*/
