老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

有长为 N 的数列，不妨设为 a1,a2,…,aN。

有如下三种操作形式：

把数列中的一段数全部乘一个值；
把数列中的一段数全部加一个值；
询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P 的值。
输入格式
第一行两个整数 N 和 P；

第二行含有 N 个非负整数，从左到右依次为 a1,a2,…,aN；

第三行有一个整数 M，表示操作总数；

从第四行开始每行描述一个操作，输入的操作有以下三种形式：

操作 1：1 t g c，表示把所有满足 t≤i≤g 的 ai 改为 ai×c；
操作 2：2 t g c，表示把所有满足 t≤i≤g 的 ai 改为 ai+c；
操作 3：3 t g，询问所有满足 t≤i≤g 的 ai 的和模 P 的值。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输出格式
对每个操作 3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

数据范围
1≤N,M≤105,
1≤t≤g≤N,
0≤c,ai≤109,
1≤P≤109
输入样例：
7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7
输出样例：
2
35
8
样例解释
初始时数列为 {1,2,3,4,5,6,7}；

经过第 1 次操作后，数列为 {1,10,15,20,25,6,7}；

对第 2 次操作，和为 10+15+20=45，模 43 的结果是 2；

经过第 3 次操作后，数列为 {1,10,24,29,34,15,16}；

对第 4 次操作，和为 1+10+24=35，模 43 的结果是 35；

对第 5 次操作，和为 29+34+15+16=94，模 43 的结果是 8。

#include<bits/stdc++.h>
using namespace std;
const   int N=100010;
int n,p;
int m;
typedef long long ll;
struct node{
    int l;
    int r;
    ll sum;
    int mul,add;
}tr[N*4];
int w[N];
void pushup(int u)
{
    tr[u].sum=(tr[u<<1|1].sum+tr[u<<1].sum)%p;
}
void eva(int u,int fa)
{

    tr[u].sum=((ll)tr[u].sum*tr[fa].mul+(ll)tr[fa].add*(tr[u].r-tr[u].l+1))%p;
         tr[u].mul=((ll)tr[u].mul*tr[fa].mul)%p;
    tr[u].add=((ll)tr[u].add*tr[fa].mul+tr[fa].add)%p;

}
void pushdown(int u)
{
    eva(u<<1,u);
    eva(u<<1|1,u);
    tr[u].mul=1;
    tr[u].add=0;
    return ;
}
void build(int u,int l,int r)
{
    tr[u]={l,r,0,1,0};
    if(l==r)
    {
        tr[u].sum=w[r];
    }
    else
    {
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int mul,int add)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        tr[u].sum=((ll)tr[u].sum*mul+(ll)add*(tr[u].r-tr[u].l+1))%p;
        tr[u].mul=((ll)tr[u].mul*mul)%p;
        tr[u].add=((ll)add+(ll)tr[u].add*mul)%p;
        return ;
    }
    else
    {
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)  modify(u<<1,l,r,mul,add);
        if(r>mid)   modify(u<<1|1,l,r,mul,add);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    return tr[u].sum;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    ll ans=0;
    if(l<=mid)  ans= query(u<<1,l,r);
    if(r>mid)   ans+= query(u<<1|1,l,r);
    return ans%p;
}
int main()
{
    cin>>n>>p;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    build(1,1,n);
    cin>>m;
    while(m--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int l,r,d;
            cin>>l>>r>>d;
            modify(1,l,r,d,0);
        }
        else if(op==2)
        {
            int l,r,d;
            cin>>l>>r>>d;
            modify(1,l,r,1,d);
        }
        else
        {
            int l,r;
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}