#include "candies.h"

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceil(x,y) (x/y)+(x%y!=0)*(x*y<0?0:1)
#define floor(x,y) (x/y)+(x%y!=0)*(x*y<0?-1:0)
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;
int tree[1<<20],lazy[1<<20];
int upd(int ni,int ns,int ne,int nl,int nr,int val){
	if(ns>nr||ne<nl)
		return tree[ni];
	if(ns>=nl&&ne<=nr){
		lazy[ni]+=val;
		return tree[ni]+=val;
	}
	int mid=ns+(ne-ns)/2;
	int l=ni*2+1,r=ni*2+2;
	if(lazy[ni]){
		tree[l]+=lazy[ni];
		tree[r]+=lazy[ni];
		lazy[l]+=lazy[ni];
		lazy[r]+=lazy[ni];
		lazy[ni]=0;
	}
	return tree[ni]=max(upd(l,ns,mid,nl,nr,val),upd(r,mid+1,ne,nl,nr,val));
}
int query(int ni,int ns,int ne,int idx){
	if(ns>idx||ne<idx)
		return 0;
	if(ns==ne)
		return tree[ni];
	int mid=ns+(ne-ns)/2;
	int l=ni*2+1,r=ni*2+2;
	if(lazy[ni]){
		tree[l]+=lazy[ni];
		tree[r]+=lazy[ni];
		lazy[l]+=lazy[ni];
		lazy[r]+=lazy[ni];
		lazy[ni]=0;
	}
	return max(query(l,ns,mid,idx),query(r,mid+1,ne,idx));
}
vector<in> distribute_candies(vector<in> c, vector<in> l, vector<in> r, vector<in> v) {
    int n = c.size(),q=l.size();
    vector<in> ans(n);
    if(n<=2000&&q<=2000){
	    for(int i=0;i<q;i++){
	    	for(int j=l[i];j<=r[i];j++){
	    		if(v[i]>0)
	    			ans[j]=min(ans[j]+v[i],c[j]);
	    		else
	    			ans[j]=max(0,ans[j]+v[i]);
	    	}
	    }
	    return ans;
	}
	for(int i=0;i<q;i++)
		upd(0,0,n-1,l[i],r[i],v[i]);
	for(int i=0;i<n;i++)
		ans[i]=min(c[i],query(0,0,n-1,i));
	return ans;
}