#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename T> vector<int32_t> normalize(vector<T> &arr){vector<int32_t> rv;rv.resize(arr.size());for (int i = 0; i < rv.size(); ++i){rv[i]=arr[i];}return rv;}
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define int long long
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "candies.h"
struct LSegTree{
vector<int> segtree;
vector<int> lazy;
LSegTree(int n){
segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
lazy.resize(segtree.size(), 0ll);
}
void dallan(int node, int sz){
segtree[node]+=sz*lazy[node];
if (sz!=1){
lazy[node*2+1]+=lazy[node];
lazy[node*2+2]+=lazy[node];
}
lazy[node]=0ll;
}
void update(int tarl, int tarr, int val, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
dallan(node,r-l+1);
if (l>=tarl && r<=tarr){
lazy[node]+=val;
dallan(node,r-l+1);
return;
}
if (l>tarr || r<tarl) return;
int mid = l+(r-l)/2;
update(tarl, tarr, val, l, mid, node*2+1);
update(tarl, tarr, val, mid+1, r, node*2+2);
segtree[node]=segtree[node*2+1]+segtree[node*2+2];
}
int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
dallan(node,r-l+1);
if (l>=tarl && r<=tarr) return segtree[node];
if (l>tarr || r<tarl) return 0ll;
int mid = l+(r-l)/2;
int lnode = query(tarl, tarr, l, mid, node*2+1);
int rnode = query(tarl, tarr, mid+1, r, node*2+2);
return lnode+rnode;
}
};//Normal Segment Tree
template<typename T> struct SegTreeBeats{
struct Node{
T sum, lazy, max1, max2, min1, min2, maxc, minc;
Node():sum(0),lazy(0),max1(0),min1(0),max2(-INF),min2(INF),minc(1),maxc(1){}
};
vector<Node> segtree;
void merge(int node){
segtree[node].sum=segtree[node*2+1].sum+segtree[node*2+2].sum;
if (segtree[node*2+1].max1==segtree[node*2+2].max1){
segtree[node].max1=segtree[node*2+1].max1;
segtree[node].maxc=segtree[node*2+1].maxc+segtree[node*2+2].maxc;
segtree[node].max2=max(segtree[node*2+1].max2,segtree[node*2+2].max2);
}
else if (segtree[node*2+1].max1>segtree[node*2+2].max1){
segtree[node].max1=segtree[node*2+1].max1;
segtree[node].maxc=segtree[node*2+1].maxc;
segtree[node].max2=max(segtree[node*2+1].max2,segtree[node*2+2].max1);
}
else {
segtree[node].max1=segtree[node*2+2].max1;
segtree[node].maxc=segtree[node*2+2].maxc;
segtree[node].max2=max(segtree[node*2+2].max2,segtree[node*2+1].max1);
}
if (segtree[node*2+1].min1==segtree[node*2+2].min1){
segtree[node].min1=segtree[node*2+1].min1;
segtree[node].minc=segtree[node*2+1].minc+segtree[node*2+2].minc;
segtree[node].min2=min(segtree[node*2+1].min2,segtree[node*2+2].min2);
}
else if (segtree[node*2+1].min1<segtree[node*2+2].min1){
segtree[node].min1=segtree[node*2+1].min1;
segtree[node].minc=segtree[node*2+1].minc;
segtree[node].min2=min(segtree[node*2+1].min2,segtree[node*2+2].min1);
}
else {
segtree[node].min1=segtree[node*2+2].min1;
segtree[node].minc=segtree[node*2+2].minc;
segtree[node].min2=min(segtree[node*2+2].min2,segtree[node*2+1].min1);
}
}
void upd_lazy(int node, int val, int sz){
segtree[node].sum+=val*sz;
segtree[node].max1+=val;
segtree[node].min1+=val;
segtree[node].lazy+=val;
if (segtree[node].max2!=-INF) segtree[node].max2+=val;
if (segtree[node].min2!=INF) segtree[node].min2+=val;
}
void upd_chmin(int node, int val, int sz){
if (val>=segtree[node].max1) return;
segtree[node].sum-=segtree[node].max1*segtree[node].maxc;
segtree[node].max1=val;
segtree[node].sum+=segtree[node].max1*segtree[node].maxc;
if (sz==1){
segtree[node].min1=segtree[node].max1;
}
else {
if (val<=segtree[node].min1) segtree[node].min1=val;
else if (val<=segtree[node].min2) segtree[node].min2=val;
}
}
void upd_chmax(int node, int val, int sz){
if (val<=segtree[node].min1) return;
segtree[node].sum-=segtree[node].min1*segtree[node].minc;
segtree[node].min1=val;
segtree[node].sum+=segtree[node].min1*segtree[node].minc;
if (sz==1){
segtree[node].max1=segtree[node].min1;
}
else {
if (val>=segtree[node].max1) segtree[node].max1=val;
else if (val>=segtree[node].max2) segtree[node].max2=val;
}
}
void dallan(int node, int sz){
if (sz==1) return;
upd_lazy(node*2+1,segtree[node].lazy,sz/2);
upd_lazy(node*2+2,segtree[node].lazy,sz/2);
segtree[node].lazy=0;
upd_chmin(node*2+1,segtree[node].max1,sz/2);
upd_chmin(node*2+2,segtree[node].max1,sz/2);
upd_chmax(node*2+1,segtree[node].min1,sz/2);
upd_chmax(node*2+2,segtree[node].min1,sz/2);
}
SegTreeBeats(int n){
segtree.resize(tol(ceil(log2(n)+1))-1);
for (int i = segtree.size()/2-1; i >= 0; i--){
merge(i);
}
}
SegTreeBeats(vector<T> v){
segtree.resize(tol(ceil(log2(v.size())+1))-1);
for (int i = 0; i < v.size(); i++){
segtree[i+segtree.size()/2].sum=segtree[i+segtree.size()/2].max1=segtree[i+segtree.size()/2].min1=v[i];
}
for (int i = segtree.size()/2-1; i >= 0; i--){
merge(i);
}
}
void chmin(int tarl, int tarr, int val, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
if (l>tarr || r<tarl || val>=segtree[node].max1) return;
if (l>=tarl && r<=tarr && val>segtree[node].max2){
upd_chmin(node,val,r-l+1);
return;
}
dallan(node,r-l+1);
int mid = l+(r-l)/2;
chmin(tarl, tarr, val, l, mid, node*2+1);
chmin(tarl, tarr, val, mid+1, r, node*2+2);
merge(node);
}
void chmax(int tarl, int tarr, int val, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
if (l>tarr || r<tarl || val<=segtree[node].min1) return;
if (l>=tarl && r<=tarr && val<segtree[node].min2){
upd_chmax(node,val,r-l+1);
return;
}
dallan(node,r-l+1);
int mid = l+(r-l)/2;
chmax(tarl, tarr, val, l, mid, node*2+1);
chmax(tarl, tarr, val, mid+1, r, node*2+2);
merge(node);
}
void update(int tarl, int tarr, int val, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
if (l>=tarl && r<=tarr) {
upd_lazy(node,val,r-l+1);
return;
}
if (l>tarr || r<tarl) return;
dallan(node,r-l+1);
int mid = l+(r-l)/2;
update(tarl, tarr, val, l, mid, node*2+1);
update(tarl, tarr, val, mid+1, r, node*2+2);
merge(node);
}
int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
if (l>=tarl && r<=tarr) return segtree[node].sum;
if (l>tarr || r<tarl) return 0;
dallan(node,r-l+1);
int mid = l+(r-l)/2;
int lnode = query(tarl, tarr, l, mid, node*2+1);
int rnode = query(tarl, tarr, mid+1, r, node*2+2);
return lnode+rnode;
}
};//SegTreeBeats
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
int n = c.size(), q = l.size();
if (*min_element(c.begin(),c.end())!=*max_element(c.begin(), c.end())){
if (n<=2000 && q<=2000){
vector<int> arr(n);
for (int i = 0; i < q; ++i)
{
for (int j = l[i]; j <= r[i]; j++){
arr[j]+=v[i];
if (arr[j]<0) arr[j]=0;
if (arr[j]>c[j]) arr[j]=c[j];
}
}
return normalize(arr);
}
LSegTree segtree(n);
for (int i = 0; i < q; ++i)
{
segtree.update(l[i],r[i],v[i]);
}
vector<int> arr(n,0);
for (int i = 0; i < n; ++i)
{
arr[i]=segtree.query(i,i);
if (arr[i]<0) arr[i]=0;
if (arr[i]>c[i]) arr[i]=c[i];
}
return normalize(arr);
}
SegTreeBeats<int> segtree(n);
for (int i = 0; i < q; i++){
segtree.update(l[i],r[i],v[i]);
segtree.chmin(l[i],r[i],c[0]);
segtree.chmax(l[i],r[i],0);
}
vector<int> arr(n);
for (int i = 0; i < n; i++){
arr[i]=segtree.query(i,i);
}
return normalize(arr);
}
