class RAQxRMQ{
private:
ll dat[2*N],laz[2*N];
ll eval(ll k){
dat[k]+=laz[k];
if(k<N)laz[k*2]+=laz[k],laz[k*2+1]+=laz[k];
laz[k]=0;return dat[k];
}
public:
void Init(){
lol(i,2*N)dat[i]=laz[i]=0;
}
void Upd(ll l,ll r,ll x){
l+=N,r+=N+1;
for(ll a=l,b=r;a<b;a>>=1,b>>=1){
if(a&1)laz[a++]+=x;
if(b&1)laz[--b]+=x;
}
for(ll a=l,b=r;a;a>>=1,b>>=1){
dat[a/2]=min(eval(a),eval(a^1));
dat[b/2]=min(eval(b),eval(b^1));
}
}
ll Qry(ll l,ll r){
l+=N,r+=N+1;
for(ll i=20;i;i--)eval(l>>i),eval(r>>i);
ll res=(ll)mod*(ll)mod;
for(ll a=l,b=r;a<b;a>>=1,b>>=1){
if(a&1)res=min(res,eval(a++));
if(b&1)res=min(res,eval(--b));
}
return res;
}
};
