#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=5e4+7;
int a[N],b[N],id[N],n,len,s[N],mod;
void add(int l,int r,int x){
    if(id[l]==id[r]){
        for(int i=l;i<=r;i++)a[i]=(a[i]+x),s[id[l]]=(s[id[l]]+x);
        return;
    }
    for(int i=l;id[i]==id[l];i++)a[i]=(a[i]+x),s[id[l]]=(s[id[l]]+x);
    for(int i=id[l]+1;i<id[r];i++)b[i]=(b[i]+x),s[i]=(s[i]+len*x);
    for(int i=r;id[i]==id[r];i--)a[i]=(a[i]+x),s[id[r]]=(s[id[r]]+x);
}
int query(int l,int r){
    int ans=0;
    if(id[l]==id[r]){
        for(int i=l;i<=r;i++)ans=(ans+a[i]+b[id[l]]);
        return (ans%mod+mod)%mod;
    }
    for(int i=l;id[i]==id[l];i++)ans=(ans+a[i]+b[id[l]]);
    for(int i=id[l]+1;i<id[r];i++)ans=(ans+s[i]);
    for(int i=r;id[i]==id[r];i--)ans=(ans+a[i]+b[id[r]]);
    return (ans%mod+mod)%mod;
}
signed main(){
    cin>>n;
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        id[i]=(i-1)/len+1;
        s[id[i]]=s[id[i]]+a[i];
    }
    for(int i=1;i<=n;i++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(opt==0)add(l,r,c);
        else{
            mod=c+1;
            printf("%lld\n",query(l,r));
        }
    }
}