#include"wall.h"
#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define int long long
using namespace std;
int mn[2000005],mx[2000005];
void push(int v){
if(mn[v]!=-1)mn[v*2]=mn[v*2]==-1?mn[v]:min(mn[v*2],mn[v]),mx[v*2]=max(mx[v*2],mn[v]),mn[v*2+1]=mn[v*2+1]==-1?mn[v]:min(mn[v*2+1],mn[v]),mx[v*2+1]=max(mx[v*2+1],mn[v]),mn[v]=-1;
if(mx[v]!=-1)mx[v*2]=mx[v*2]==-1?mx[v]:max(mx[v*2],mx[v]),mn[v*2]=mn[v*2]==-1?-1:max(mn[v*2],mx[v]),mx[v*2+1]=mx[v*2+1]==-1?mx[v]:max(mx[v*2+1],mx[v]),mn[v*2+1]=mn[v*2+1]==-1?-1:max(mn[v*2+1],mx[v]),mx[v]=-1;
}
void um(int v,int tl,int tr,int l,int r,int val){
if(l>r)return;
if(l==tl&&r==tr)return mn[v]=mn[v]==-1?val:min(mn[v],val),mx[v]=max(mx[v],val),void();
push(v);
int tm=(tl+tr)>>1;
um(v*2,tl,tm,l,min(r,tm),val),um(v*2+1,tm+1,tr,max(l,tm+1),r,val);
}
void ux(int v,int tl,int tr,int l,int r,int val){
if(l>r)return;
if(l==tl&&r==tr)return mx[v]=mx[v]==-1?val:max(mx[v],val),mn[v]=mn[v]==-1?-1:max(mn[v],val),void();
push(v);
int tm=(tl+tr)>>1;
ux(v*2,tl,tm,l,min(r,tm),val),ux(v*2+1,tm+1,tr,max(l,tm+1),r,val);
}
void get(int v,int tl,int tr,int*a){
if(tl==tr)return a[tl]=mx[v]==-1?0:max(0LL,mn[v]==-1?mx[v]:min(mn[v],mx[v])),void();
push(v);
int tm=(tl+tr)>>1;
get(v*2,tl,tm,a),get(v*2+1,tm+1,tr,a);
}
void buildWall(int n,int k,int op[],int l[],int r[],int h[],int f[]){
memset(mn,-1,sizeof mn),memset(mx,-1,sizeof mx);
for(int i=0;i<k;i++)op[i]==1?ux(1,0,n-1,l[i],r[i],h[i]):um(1,0,n-1,l[i],r[i],h[i]);
get(1,0,n-1,f);
}
