wa on #11~14

#include<iostream>
#define N 200005
#define gc getchar
#define pc putchar
#define int long long
#define ls(x) (x<<1)
#define rs(x) (ls(x)+1)
using namespace std;
int n,q,w,a[N],L,R,mid,ans,l,r,d,he;
int rd(){
	int x=0,f=1;
	char c=gc();
	for(;!isdigit(c);c=gc())f=c==45?-1:f;
	for(;isdigit(c);c=gc())x=x*10+(c^48);
	return x*f;
}
void wr(int x){
	if(!x)return;
	if(x<0)pc(45),x=-x;
	wr(x/10),pc(x%10|48);
}
struct node {
	int l,r,sum,tag;
} tr[N<<2];
void push_up(int u) {
	tr[u].sum=tr[ls(u)].sum+tr[rs(u)].sum;
}
void build(int u,int x,int y) {
	tr[u].l=x,tr[u].r=y;
	if(y==x)tr[u].sum=a[x];
	else {
		int mid=(x+y)>>1;
		build(ls(u),x,mid),build(rs(u),mid+1,y);
		push_up(u);
	}
}
void mk_tag(int u,int Tag) {
	tr[u].tag+=Tag;
	tr[u].sum+=Tag*(tr[u].r-tr[u].l+1);
}
void push_down(int u) {
	mk_tag(ls(u),tr[u].tag);
	mk_tag(rs(u),tr[u].tag);
	tr[u].tag=0;
}
int query(int u,int l,int r) {
	if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;
	if(l>tr[u].r||r<tr[u].l)return 0;
	push_down(u);
	return query(ls(u),l,r)+query(rs(u),l,r);
}
void add(int u,int l,int r,int num) {
	if(l<=tr[u].l&&tr[u].r<=r) {
		mk_tag(u,num);
		return;
	}
	if(l>tr[u].r||r<tr[u].l)return;
	push_down(u);
	add(ls(u),l,r,num),add(rs(u),l,r,num);
	push_up(u);
}
int dfs(int u,int l,int r,int T,int hp){
	if(l==r) return 1;
	int mid=tr[ls(u)].r;
	push_down(u);
	if(tr[ls(u)].sum*T>=hp)return dfs(ls(u),l,mid,T,hp);
	return (mid-l+1)+dfs(rs(u),mid+1,r,T,hp-tr[ls(u)].sum*T);
}
void solve() {
	int T=0,Res=w;
	while(Res>=(he<<T)){
		Res-=he<<T,T++;
	}
	if(!Res){
		wr(T*n-1),puts("");return;
	}
	int ans=T*n;
	wr(dfs(1,1,n,1<<T,Res)+ans-1),puts("");
}

signed main() {
	n=rd(),q=rd(),w=rd();
	for(int i=1;i<=n;i++)he+=a[i]=rd();
	build(1,1,n);
	while(q--) {
		l=rd(),r=rd(),d=rd();
		add(1,l,r,d);
		he+=(r-l+1)*d;
		solve();
	}
	return 0;
}