維護序列

老師交給小可可一個維護數列的任務，現在小可可希望你來幫他完成。

有長為 n 的數列，不妨設為 a1,a2,⋯,an。有如下三種操作形式：

把數列中的一段數全部乘一個值；

把數列中的一段數全部加一個值；

詢問數列中的一段數的和，由于答案可能很大，你隻需輸出這個數模 P 的值。

Input

第一行兩個整數 n 和 P；

第二行含有 n 個非負整數，從左到右依次為 a1,a2,⋯,an；

第三行有一個整數 M，表示操作總數；

從第四行開始每行描述一個操作，輸入的操作有以下三種形式：

Output

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 0x7f7f7f7f;
ll n,p;
ll a[400010];
struct node
{
    ll sum,cheng,jia;
}tree[400001];
void up(ll now)
{
    tree[now].sum = (tree[now<<1].sum + tree[now<<1|1].sum) % p;
}
void build(ll now,ll l,ll r)//建樹
{
    tree[now].cheng = 1;
    if(l == r)
    {
        tree[now].sum = a[l];
        return ;
    }
    int mid = (l+r) / 2;
    build(now<<1, l, mid);
    build(now<<1|1,mid + 1, r);
    up(now);
}
void down(ll now,ll l,ll r)
{
    ll ls = now<<1,rs = now<<1|1, mid = (l+r)>>1;
    tree[ls].sum = (tree[ls].sum * tree[now].cheng % p + tree[now].jia * (mid-l+1) % p) % p;
    tree[ls].cheng = (tree[ls].cheng * tree[now].cheng) % p;
    tree[ls].jia = (tree[ls].jia * tree[now].cheng + tree[now].jia) %p;
    tree[rs].sum = (tree[rs].sum * tree[now].cheng % p + tree[now].jia * (r-(mid+1)+1) % p) %p;
    tree[rs].cheng = (tree[rs].cheng * tree[now].cheng) % p;
    tree[rs].jia = (tree[rs].jia * tree[now].cheng + tree[now].jia) % p;
    tree[now].jia = 0;
    tree[now].cheng = 1;
    return ;
}
void mul(ll now,ll l,ll r,ll x,ll y,ll k)
{
    if(r<x || l>y) 
    return ;
    if(l >= x && r <= y)
    {
        tree[now].sum = (tree[now].sum * k) % p;
        tree[now].cheng = (tree[now].cheng * k) % p;
        tree[now].jia = (tree[now].jia * k) % p;
        return ;
    }
    down(now,l,r);
    ll mid = (l+r) >> 1;
    mul(now << 1,l,mid,x,y,k);
    mul(now << 1 | 1,mid + 1,r,x,y,k);
    up(now);
}
void add(ll now,ll l,ll r,ll x,ll y,ll k)
{
    if(r < x || l > y) 
    return ;
    if(l >= x && r <= y)
    {
        tree[now].sum = (tree[now].sum + k * (r-l+1) % p) %p;
        tree[now].jia = (tree[now].jia+k) % p;
        return ;
    }
    down(now,l,r);
    ll mid = (l+r) >> 1;
    add(now << 1,l,mid,x,y,k);
    add(now << 1 | 1,mid + 1,r,x,y,k);
    up(now);
}
int answer(ll now,ll l,ll r,ll x,ll y)//區間求和
{
    if(r < x || l > y) 
    return 0;
    if(l >= x && r <= y)
    return tree[now].sum;
    down(now,l,r);
    ll mid = (l+r) >> 1;
    return (answer(now<<1,l,mid,x,y) + answer(now<<1|1,mid+1,r,x,y)) % p;
}
int main()
{
    scanf("%lld%lld",&n,&p);
    for(int i = 1; i <= 4*n; i++)
    {
        tree[i].cheng = 1;
    }
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    ll m;
    scanf("%lld",&m);
    while(m--)
    {
        int op;
        ll l,r,k;
        scanf("%d",&op);
        if(op == 1)
        {
            scanf("%lld%lld%lld",&l,&r,&k);
            mul(1,1,n,l,r,k);
        }
        else if(op == 2)
        {
            scanf("%lld%lld%lld",&l,&r,&k);
            add(1,1,n,l,r,k);
        }
        else
        {
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",answer(1,1,n,l,r) % p);
        }
    }
}