#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define s second
#define pb push_back
#define f first
#define all(x) x.begin(),x.end()
const int mxn=2e5,inf=1e18,minf=-1e18;
int n,q;
int C[mxn+10],L[mxn+10],R[mxn+10],V[mxn+10];
struct sub1{
static vector<int32_t>solve(){
vector<int32_t>ans(n,0);
for(int i=0;i<q;i++){
for(int j=L[i];j<=R[i];j++)ans[j]+=V[i];
for(int j=0;j<n;j++)ans[j]=max(0,ans[j]),ans[j]=min(ans[j],(int32_t)C[j]);
}
return ans;
}
};
struct sub2{
struct fen{
int fwk[mxn+10];
void init(){for(int i=0;i<=n;i++)fwk[i]=0;}
void update(int pos,int val){
pos++;
for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;
}
int qry(int pos){
int sum=0;
pos++;
if(pos<=0)return 0;
for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
if(sum<0)assert(0);
return sum;
}
};
static vector<int32_t>solve(){
fen t;
t.init();
vector<int32_t>ans(n,0);
int sum=0;
for(int i=0;i<q;i++){
t.update(L[i],V[i]);
t.update(R[i]+1,-V[i]);
}
for(int i=0;i<n;i++){
int x=min(C[i],t.qry(i));
ans[i]=(int32_t)x;
}
return ans;
}
};
int mn[4*mxn+10],mn2[4*mxn+10];
int lazy[4*mxn+10],O[4*mxn+10];
int tag1[4*mxn+10],tag2[4*mxn+10];
struct seg{
//original array
//lazy , get min , set to 0 , set to C[i]
//qry for the prefix <0
void pull(int pos){
mn[pos]=min(mn[pos<<1],mn[pos<<1|1]);
mn2[pos]=min(mn2[pos<<1],mn2[pos<<1|1]);
}
void build(int pos=1,int l=0,int r=n-1){
if(l==r){
O[pos]=C[l];
mn2[pos]=O[pos];
return;
}
mn[pos]=0;
tag1[pos]=lazy[pos]=tag2[pos]=0;
int mid=l+(r-l)/2;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
pull(pos);
O[pos]=min(O[pos<<1],O[pos<<1|1]);
}
void apply1(int x,int pos){
mn[pos]+=x;
mn2[pos]-=x;
lazy[pos]+=x;
}
void apply2(int x,int pos){
if(!x)return;
//tag1
mn[pos]=0;
mn2[pos]=O[pos];
tag2[pos]=lazy[pos]=0;
tag1[pos]=1;
}
void apply3(int x,int pos){
if(!x)return;
mn[pos]=O[pos];
mn2[pos]=0;
tag1[pos]=lazy[pos]=0;
tag2[pos]=1;
}
void push(int pos,int l,int r){
if(l!=r){
apply2(tag1[pos],pos<<1);
apply2(tag1[pos],pos<<1|1);
apply3(tag2[pos],pos<<1);
apply3(tag2[pos],pos<<1|1);
apply1(lazy[pos],pos<<1);
apply1(lazy[pos],pos<<1|1);
}
lazy[pos]=tag1[pos]=tag2[pos]=0;
}
void update1(int ql,int qr,int val,int pos=1,int l=0,int r=n-1){
if(ql>r||qr<l)return;
if(ql<=l&&r<=qr)return void(apply1(val,pos));
int mid=l+(r-l)/2;
push(pos,l,r);
update1(ql,qr,val,pos<<1,l,mid);
update1(ql,qr,val,pos<<1|1,mid+1,r);
pull(pos);
}
void update2(int ql,int qr,int val=1,int pos=1,int l=0,int r=n-1){
if(ql>r||qr<l)return;
if(ql<=l&&r<=qr)return void(apply2(val,pos));
int mid=l+(r-l)/2;
push(pos,l,r);
update2(ql,qr,val,pos<<1,l,mid);
update2(ql,qr,val,pos<<1|1,mid+1,r);
pull(pos);
}
void update3(int ql,int qr,int val=1,int pos=1,int l=0,int r=n-1){
if(ql>r||qr<l)return;
if(ql<=l&&r<=qr)return void(apply3(val,pos));
int mid=l+(r-l)/2;
push(pos,l,r);
update3(ql,qr,val,pos<<1,l,mid);
update3(ql,qr,val,pos<<1|1,mid+1,r);
pull(pos);
}
int qry1(int ql,int qr,int pos=1,int l=0,int r=n-1){
if(ql>r||qr<l)return inf;
if(ql<=l&&r<=qr)return mn[pos];
int mid=l+(r-l)/2;
push(pos,l,r);
return min(qry1(ql,qr,pos<<1,l,mid),qry1(ql,qr,pos<<1|1,mid+1,r));
}
int qry2(int ql,int qr,int pos=1,int l=0,int r=n-1){
if(ql>r||qr<l)return inf;
if(ql<=l&&r<=qr)return mn2[pos];
int mid=l+(r-l)/2;
push(pos,l,r);
return min(qry2(ql,qr,pos<<1,l,mid),qry2(ql,qr,pos<<1|1,mid+1,r));
}
};
struct sub4{
static vector<int32_t>solve(){
vector<int32_t>ans(n);
vector<pii>ord;
seg t;
for(int i=0;i<n;i++)ord.pb({C[i],i});
sort(C,C+n);
sort(all(ord));
t.build();
for(int i=0;i<q;i++){
t.update1(L[i],R[i],V[i]);
int pos=-1;
int l=0,r=n-1;
while(l<=r){
int mid=l+(r-l)/2;
if(t.qry1(mid,mid)<0)l=mid+1,pos=max(pos,mid);
else r=mid-1;
}
if(pos!=-1)t.update2(0,pos);
l=0,r=n-1,pos=-1;
while(l<=r){
int mid=l+(r-l)/2;
if(t.qry2(mid,mid)<0)l=mid+1,pos=max(pos,mid);
else r=mid-1;
}
if(pos!=-1)t.update3(0,pos);
}
for(int i=0;i<n;i++){
ans[ord[i].s]=t.qry1(i,i);
}
return ans;
}
};
int sum[4*mxn+10];
int mx1[4*mxn+10],mx2[4*mxn+10],mxc[4*mxn+10],mn1[4*mxn+10],mnc[4*mxn+10];
struct segbeat{
//min,max,add
//chmin
void apply1(int pos, int x,int l,int r){
if(mx1[pos]<=x)return;
//mx2[pos] <= x < mx1[pos] ->update only mx1[pos]
sum[pos]-=mx1[pos]*mxc[pos];
mx1[pos]=x;
sum[pos]+=mx1[pos]*mxc[pos];
if(l==r)mn1[pos]=x;
else{
//case mx1 intersects mn1,mn2
if(x<=mn1[pos])mn1[pos]=x;
else if(x<mn2[pos])mn2[pos]=x;
}
//lazy[pos]=0;
}
void apply2(int pos, int x,int l,int r){
if(mn1[pos]>=x)return;
//mn1[pos] <= x < mn2[pos]
sum[pos]-=mn1[pos]*mnc[pos];
mn1[pos]=x;
sum[pos]+=mn1[pos]*mnc[pos];
if(l==r)mx1[pos]=x;
else{
if(x>=mx1[pos])mx1[pos]=x;
else if(x>mx2[pos])mx2[pos]=x;
}
//lazy[pos]=0;
}
void apply3(int pos,int x,int l,int r){
sum[pos]+=(r-l+1)*x;
mx1[pos]+=x;
if(mx2[pos]!=minf)mx2[pos]+=x;
mn1[pos]+=x;
if(mn2[pos]!=inf)mn2[pos]+=x;
lazy[pos]+=x;
}
void push(int pos,int l,int r){
if(l!=r){
int mid=l+(r-l)/2;
apply3(pos<<1,lazy[pos],l,mid);
apply3(pos<<1|1,lazy[pos],mid+1,r);
apply1(pos<<1,mx1[pos],l,mid);
apply1(pos<<1|1,mx1[pos],mid+1,r);
apply2(pos<<1,mn1[pos],l,mid);
apply2(pos<<1|1,mn1[pos],mid+1,r);
}
lazy[pos]=0;
}
void pull(int pos,int l,int r){
sum[pos]=sum[pos<<1]+sum[pos<<1|1];
if(mx1[pos<<1]==mx1[pos<<1|1]){
mx1[pos]=mx1[pos<<1];
mx2[pos]=max(mx2[pos<<1],mx2[pos<<1|1]);
mxc[pos]=mxc[pos<<1]+mxc[pos<<1|1];
}
else{
if(mx1[pos<<1]>mx1[pos<<1|1]){
mx1[pos]=mx1[pos<<1];
mx2[pos]=max(mx1[pos<<1|1],mx2[pos<<1]);
mxc[pos]=mxc[pos<<1];
}
else{
mx1[pos]=mx1[pos<<1|1];
mx2[pos]=max(mx1[pos<<1],mx2[pos<<1|1]);
mxc[pos]=mxc[pos<<1|1];
}
}
if(mn1[pos<<1]==mn1[pos<<1|1]){
mn1[pos]=mn1[pos<<1];
mn2[pos]=min(mn2[pos<<1],mn2[pos<<1|1]);
mnc[pos]=mnc[pos<<1]+mnc[pos<<1|1];
}
else{
if(mn1[pos<<1]<mn1[pos<<1|1]){
mn1[pos]=mn1[pos<<1];
mn2[pos]=min(mn1[pos<<1|1],mn2[pos<<1]);
mnc[pos]=mnc[pos<<1];
}
else{
mn1[pos]=mn1[pos<<1|1];
mn2[pos]=min(mn1[pos<<1],mn2[pos<<1|1]);
mnc[pos]=mnc[pos<<1|1];
}
}
}
void build(int pos=1,int l=0,int r=n-1){
lazy[pos]=0;
if(l==r){
sum[pos]=mx1[pos]=mn1[pos]=0;
mx2[pos]=minf;
mn2[pos]=inf;
mnc[pos]=mxc[pos]=1;
return;
}
int mid=l+(r-l)/2;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
pull(pos,l,r);
}
//chmin
void update1(int ql,int qr,int x,int pos=1,int l=0,int r=n-1){
if(l>qr||r<ql||mx1[pos]<=x)return;
if(ql<=l&&r<=qr&&mx2[pos]<x)return void(apply1(pos,x,l,r));
int mid=l+(r-l)/2;
push(pos,l,r);
update1(ql,qr,x,pos<<1,l,mid);
update1(ql,qr,x,pos<<1|1,mid+1,r);
pull(pos,l,r);
}
void update2(int ql,int qr,int x,int pos=1,int l=0,int r=n-1){
if(l>qr||r<ql||mn1[pos]>=x)return;
if(ql<=l&&r<=qr&&mn2[pos]>x)return void(apply2(pos,x,l,r));
int mid=l+(r-l)/2;
push(pos,l,r);
update2(ql,qr,x,pos<<1,l,mid);
update2(ql,qr,x,pos<<1|1,mid+1,r);
pull(pos,l,r);
}
void update3(int ql,int qr,int x,int pos=1,int l=0,int r=n-1){
if(l>qr||r<ql)return;
if(ql<=l&&r<=qr)return void(apply3(pos,x,l,r));
int mid=l+(r-l)/2;
push(pos,l,r);
update3(ql,qr,x,pos<<1,l,mid);
update3(ql,qr,x,pos<<1|1,mid+1,r);
pull(pos,l,r);
}
int qry(int ql,int qr,int pos=1,int l=0,int r=n-1){
if(l>qr||r<ql)return 0;
if(ql<=l&&r<=qr)return sum[pos];
int mid=l+(r-l)/2;
push(pos,l,r);
return qry(ql,qr,pos<<1,l,mid)+qry(ql,qr,pos<<1|1,mid+1,r);
}
};
struct sub3{
static vector<int32_t>solve(){
segbeat t;
t.build();
for(int i=0;i<q;i++){
t.update3(L[i],R[i],V[i]);
t.update1(L[i],R[i],C[0]);
t.update2(L[i],R[i],0);
}
vector<int32_t>ans;
for(int i=0;i<n;i++)ans.pb(t.qry(i,i));
return ans;
}
};
vector<int32_t> distribute_candies(vector<int32_t> c,vector<int32_t> l,vector<int32_t> r,vector<int32_t> v) {
n=c.size(),q=l.size();
for(int i=0;i<n;i++)C[i]=c[i];
for(int i=0;i<q;i++)L[i]=l[i],R[i]=r[i],V[i]=v[i];
int yes=1,yes2=1;
for(auto i:v)if(i<0)yes=0;
for(int i=0;i<q;i++)yes2&=(l[i]==0&&r[i]==n-1);
if(n<=2000&&q<=2000)return sub1::solve();
else if(yes)return sub2::solve();
else if(yes2)return sub4::solve();
else return sub3::solve();
}
/*
10
11 440 51 41 11 1 3 108 148 14
10
0 9 60
0 9 -9
0 9 -30
0 9 41
0 9 82
0 9 69
0 9 -79
0 9 -39
0 9 72
0 9 41
*/
