#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 int long long
#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],tree2[1<<20],lazy[1<<20],cc,mnd[200010],mxd[200010],cur[200010];
void upd(int ni,int ns,int ne,int nl,int nr,int val){
	if(ns>nr||ne<nl)
		return;
	if(ns>=nl&&ne<=nr){
		lazy[ni]+=val;
		tree[ni]+=val;
		tree2[ni]+=val;
		return;
	}
	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];
		tree2[l]+=lazy[ni];
		tree2[r]+=lazy[ni];
		lazy[l]+=lazy[ni];
		lazy[r]+=lazy[ni];
		lazy[ni]=0;
	}
	upd(l,ns,mid,nl,nr,val);
	upd(r,mid+1,ne,nl,nr,val);
	tree[ni]=max(tree[l],tree[r]);
	tree2[ni]=min(tree2[l],tree2[r]);
	return;
}
int querymx(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];
		tree2[l]+=lazy[ni];
		tree2[r]+=lazy[ni];
		lazy[l]+=lazy[ni];
		lazy[r]+=lazy[ni];
		lazy[ni]=0;
	}
	return max(querymx(l,ns,mid,idx),querymx(r,mid+1,ne,idx));
}
int querymn(int ni,int ns,int ne,int idx){
	if(ns>idx||ne<idx)
		return 0;
	if(ns==ne)
		return tree2[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];
		tree2[l]+=lazy[ni];
		tree2[r]+=lazy[ni];
		lazy[l]+=lazy[ni];
		lazy[r]+=lazy[ni];
		lazy[ni]=0;
	}
	return min(querymn(l,ns,mid,idx),querymn(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;
	}
	int mn=0;
	for(int i=0;i<q;i++)
		mn=min(mn,(int)v[i]);
	if(!mn){
		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((int)c[i],querymx(0,0,n-1,i));
		return ans;
	}
	int mn0=l.size(),mnc=l.size();
	for(int i=0;i<n;i++){
		if(i<1000){
			int mx0=0,mxc=0;
			for(int j=0;j<l.size();j++){
				int x=ans[i];
				if(v[j]>0)
	    			ans[i]=min(ans[i]+v[j],c[i]);
	    		else
	    			ans[i]=max(0,ans[i]+v[j]);
	    		if(ans[i]==0)
	    			mx0=j;
	    		if(ans[i]==c[i])
	    			mxc=j;
	    		cur[j]=ans[i]-x;
	    		mnd[j]=min(mnd[j],cur[j]);
	    		mxd[j]=max(mxd[j],cur[j]);
			}
			mn0=min(mn0,mx0);
			mnc=min(mnc,mxc);
		}
		else{
			if(mnc>mn0)
				ans[i]=c[i];
			for(int j=max(mn0,mnc);j<l.size();j++){
				if(v[j]>0)
	    			ans[i]=min(ans[i]+v[j],c[i]);
	    		else
	    			ans[i]=max(0,ans[i]+v[j]);
	    		if(mnd[q-1]-mnd[j]==mxd[q-1]-mxd[j]){
	    			ans[i]+=mnd[q-1]-mnd[j];
	    			ans[i]=min(ans[i],c[i]);
	    			ans[i]=max(ans[i],0);
	    			break;
	    		}
			}
		}
	}
	return ans;
}