#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int > pii;
typedef long long int lld;
#define pi acos(-1)
#define fr(i,m,n) for(i=m;i<n;i++)
#define fu(i,m,n) for(i=m;i>=n;i--)
#define vec vector<int>
#define pb push_back
#define pp pop_back()
#define ft first
#define sd second
#define all(v) v.begin(),v.end()
#define mom(ara) memset(ara,0,sizeof(ara));
#define m1m(ara) memset(ara,-1,sizeof(ara));
#define endl "\n"
#define eps 1.19209e-07
#define at1 (at*2)
#define at2 (at*2)+1
// add is true and remove is false
int A[5000000],B[5000000];
bool opt[5000000],mark[5000000];
int ans;
void change(int at,int h,bool w)
{
if(w)
{
if(h>A[at] || (!opt[at] && B[at]<h))
{
opt[at]=w;
A[at]=h;
mark[at]=true;
}
}
else
{
if(h<B[at] || (opt[at] && A[at]>h))
{
opt[at]=w;
B[at]=h;
mark[at]=true;
}
}
}
void propagate(int l,int r,int at)
{
mark[at]=false;
if(opt[at])
{
change(at1,B[at],false);
change(at2,B[at],false);
change(at1,A[at],true);
change(at2,A[at],true);
}
else
{
change(at1,A[at],true);
change(at2,A[at],true);
change(at1,B[at],false);
change(at2,B[at],false);
}
A[at]=0;B[at]=1e9+7;
}
void update(int l,int r,int at,int L,int R,int h,bool w)
{
if(l>R || r<L) return;
if(L<=l && r<=R)
{
change(at,h,w);
return;
}
if(mark[at]) propagate(l,r,at);
int mid=(l+r)/2;
update(l,mid,at1,L,R,h,w);
update(mid+1,r,at2,L,R,h,w);
}
void query(int l,int r,int at,int pos)
{
if(l==r)
{
if(mark[at])
{
if(opt[at])
{
ans=min(B[at],ans);
ans=max(A[at],ans);
}
else
{
ans=max(A[at],ans);
ans=min(B[at],ans);
}
}
return;
}
int mid=(l+r)/2;
if(pos<=mid) query(l,mid,at1,pos);
else query(mid+1,r,at2,pos);
if(mark[at])
{
if(opt[at])
{
ans=min(B[at],ans);
ans=max(A[at],ans);
}
else
{
ans=max(A[at],ans);
ans=min(B[at],ans);
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int i;
fr(i,0,5000000) B[i]=1e9+7;
fr(i,0,k)
{
update(1,n,1,left[i]+1,right[i]+1,height[i],(op[i]==1));
}
fr(i,1,n+1)
{
ans=0;
query(1,n,1,i);
finalHeight[i-1]=ans;
}
return;
}
