线段树维护等差数列

//https://ac.nowcoder.com/acm/contest/5157/C

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

typedef pair<int,int> PII;

const int N = 200010;
const int inf=1e18;
const int mod=3*5*7*11*13*17*19*23,inv2=mod-mod/2;

int a[N];

struct node {
    int l,r,sum,k,d;   
}tr[4 * N];   

node unite(node a,node b)
{
    node temp;
    temp.l=a.l,temp.r=b.r;
    temp.sum=(a.sum+b.sum)%mod;
    temp.k=temp.d=0;
    return temp;
}

void push_up(int u)
{
    tr[u]=unite(tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u]={l,r,a[l]%mod,0,0};
        //...
        return;
    }
    tr[u].l=l,tr[u].r=r;
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    push_up(u);
}

void pushdown(int u)
{
    if(!tr[u].k&&!tr[u].d)return;
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    int len1=left.r-left.l+1;
    int k=tr[u].k,d=tr[u].d;

    left.sum=(left.sum+(k+(k+(len1-1)*d)%mod)*len1%mod*inv2%mod)%mod;
    left.k=(left.k+k)%mod,left.d=(left.d+d)%mod;

    k=(k+len1*d%mod);

    int len2=right.r-right.l+1;
    right.sum=(right.sum+(k+(k+(len2-1)*d)%mod)*len2%mod*inv2%mod)%mod;
    right.k=(right.k+k)%mod,right.d=(right.d+d)%mod;
    tr[u].k=0,tr[u].d=0;
}

void modify(int u, int l, int r,int k, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        int len=tr[u].r-tr[u].l+1;
        tr[u].sum=(tr[u].sum+(k+(k+(len-1)*d%mod)%mod)%mod*len%mod*inv2%mod)%mod;
        tr[u].k=(tr[u].k+k)%mod;
        tr[u].d=(tr[u].d+d)%mod;
    }
    else    // 一定要分裂
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) modify(u<<1, l, r,k,d);
        else if (l > mid) modify(u<<1|1, l, r,k,d);
        else
        {
            modify(u<<1,l,mid,k,d);
            k=(k+(mid-l+1)*d%mod)%mod;
            modify(u<<1|1,mid+1,r,k,d);
        }

        push_up(u);
    }
}

node query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        return tr[u];
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid)return query(u<<1,l,r);
    else if(l>mid)return query(u<<1|1,l,r);
    else
    {
        node left=query(u<<1,l,r);
        node right=query(u<<1|1,l,r);
        return unite(left,right);
    }
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    build(1,1,n);
    int q;
    cin>>q;

    while(q--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1)
        {
            int k,d;
            cin>>k>>d;
            modify(1,l,r,k%mod,d%mod);
        }
        else
        {
            int m;
            cin>>m;
            cout<<query(1,l,r).sum%m<<'\n';
        }
    }

}

signed main() 
{
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    solve();
}