#include "candies.h"
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define pll pair<ll,ll>
#define fi first
#define sc second
#define dbg(x) cerr<#x<<": "<<x<<endl;
using namespace std;
#define maxn 200005
ll n,q;
ll a[maxn],c[maxn];
vector<pll> t[2*maxn];
ll ls[2*maxn],rs[2*maxn],root = 0,tsz = 0;
void init(ll &v,ll tl,ll tr){
t[v].clear();
if(!v) v = ++tsz;
if(tl==tr) return;
ll mid = (tl+tr)/2;
init(ls[v],tl,mid);
init(rs[v],mid+1,tr);
}
void upd(ll v,ll tl,ll tr,ll l,ll r,pll p){
if(l>r||tl>tr||l>tr||tl>r) return;
if(tl>=l&&tr<=r){t[v].pb(p);return;}
ll mid = (tl+tr)/2;
upd(ls[v],tl,mid,l,r,p);
upd(rs[v],mid+1,tr,l,r,p);
}
set<pll> cur;
void reshi(ll v,ll tl,ll tr){
for(pll p : t[v]) cur.insert(p);
ll mid = (tl+tr)/2;
if(tl==tr){
ll i = tl;
for(pll p : cur){
a[i]+=p.sc;
if(a[i]<0) a[i] = 0;
if(a[i]>c[i]) a[i] = c[i];
}
goto lol;
}
reshi(ls[v],tl,mid);
reshi(rs[v],mid+1,tr);
lol:;
for(pll p : t[v]){
cur.erase(cur.find(p));
}
}
ll d = 400;
vector<int> ans;
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> VAL) {
n = C.size();
q = L.size();
for(ll i = 1;i<=n;i++) c[i] = C[i-1];
sort(a+1,a+1+n);
init(root,1,n);
for(ll i = 1;i<=q;i++){
ll l = L[i-1] + 1;
ll r = R[i-1] + 1;
ll val = VAL[i-1];
if(i%d==0){
reshi(root,1,n);
init(root,1,n);
}
upd(root,1,n,l,r,{i,val});
}
reshi(root,1,n);
for(ll i = 1;i<=n;i++) ans.pb(a[i]);
return ans;
}
