#include <bits/stdc++.h>
#define vec queries[i]
#include "candies.h"
using namespace std;
typedef long long ll;
const int LIM = 500;
const ll INF = 1e18;
int n, q;
ll cap[200002], arr[200002];
int ql[200002], qr[200002];
ll qv[200002];
pair<ll, int> sortedList[200002];
int group[200002];
bool done[200002];
vector<pair<ll, int> > queries[200002];
ll minSum, maxSum, sum, prv;
void solveQuery(int qs, int qe){
vector<int> ranges {0, n};
for(int i=qs; i<=qe; i++){
ranges.push_back(ql[i]);
ranges.push_back(qr[i]+1);
}
sort(ranges.begin(), ranges.end());
ranges.erase(unique(ranges.begin(), ranges.end()), ranges.end());
int rangeCnt = (int)ranges.size() - 1;
for(int i=0; i<rangeCnt; i++){
int l = ranges[i], r = ranges[i+1]-1;
queries[i].clear();
for(int j=l; j<=r; j++){
group[j] = i;
done[j] = 0;
}
}
for(int i=0; i<n; i++) queries[group[sortedList[i].second]].push_back(sortedList[i]);
for(int i=0; i<rangeCnt; i++){
int l = ranges[i], r = ranges[i+1]-1;
ll A=0, B=INF, C=0;
for(int j=qs; j<=qe; j++){
if(r<ql[j] || qr[j]<l) continue;
C += qv[j];
A = max(A, -C);
B = min(B, INF-C);
}
for(int j=l; j<=r; j++){
if(A + (INF-B) > cap[j]) continue;
done[j] = 1;
if(arr[j] <= A) arr[j] = A+C;
else if(cap[j] - arr[j] <= INF - B) arr[j] = B+C + (cap[j] - INF);
else arr[j] += C;
}
minSum = 0;
maxSum = sum = prv = 0;
int pnt = 0;
ll lim = 0;
for(int j=qe; j>=qs; j--){
if(r<ql[j] || qr[j]<l) continue;
sum += qv[j];
minSum = min(minSum, sum);
maxSum = max(maxSum, sum);
ll tmpMax = sum - minSum;
ll tmpMin = sum - maxSum;
if(prv >= max(tmpMax, -tmpMin)) continue;
if(prv < tmpMax){
while(pnt < (int)vec.size() && vec[pnt].first <= tmpMax){
if(!done[vec[pnt].second]) arr[vec[pnt].second] = lim + (vec[pnt].first - prv);
pnt++;
}
lim += (tmpMax - prv);
}
else{
while(pnt < (int)vec.size() && vec[pnt].first <= -tmpMin){
if(!done[vec[pnt].second]) arr[vec[pnt].second] = lim;
pnt++;
}
}
prv = max(tmpMax, -tmpMin);
}
while(pnt < (int)vec.size()){
if(!done[vec[pnt].second]) arr[vec[pnt].second] = lim;
pnt++;
}
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = (int)c.size();
for(int i=0; i<n; i++) cap[i] = c[i];
q = (int)l.size();
for(int i=0; i<q; i++){
ql[i] = l[i], qr[i] = r[i], qv[i] = v[i];
}
for(int i=0; i<n; i++) sortedList[i] = make_pair(cap[i], i);
sort(sortedList, sortedList+n);
for(int i=0; i*LIM<q; i++){
solveQuery(i*LIM, min(i*LIM+LIM-1, q-1));
}
return vector<int> (arr, arr+n);
}
