记录编号	427951	评测结果	AAAAAAAAAA
题目名称	[AHOI2009] 行星序列	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	2.267 s
提交时间	2017-07-23 23:22:52	内存使用	1.08 MiB

/***************************

    segment tree
            By Cooook.

***************************/



#include <iostream>
#include <stdio.h>
#include <cstring>
#define MAXN 100005
using namespace std;
long long p,a[MAXN];
int n;


template<typename _t>
inline _t read(){
    _t x=0,f=1;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
    return x*f;
}

struct node{
    node *ls,*rs;
    long long sum,mulit,add;
    int l,r;
    void Maintain(){
        sum=0;
        if(ls)sum=ls->sum%p;
        if(rs)sum=(sum+rs->sum)%p;
    }

    void push_down(){
        if(l==r)return;
        ls->sum=(ls->sum*mulit+add*(ls->r-ls->l+1))%p;
        ls->mulit=ls->mulit*mulit%p;
        ls->add=(ls->add*mulit+add)%p;
        rs->sum=(rs->sum*mulit%p+add*(rs->r-rs->l+1))%p;
        rs->mulit=rs->mulit*mulit%p;
        rs->add=(rs->add*mulit+add)%p;
        mulit=1;add=0;
    }

    node(){
        sum=add=0;
        mulit=1;
        ls=rs=NULL;
    }
}*root;

void build(node *&o,int l,int r){
    if(!o)o=new node();
    o->l=l;o->r=r;
    if(l==r){
        o->sum=read<long long>()%p;
        return;
    }
    int m=l+r>>1;
    build(o->ls,l,m);
    build(o->rs,m+1,r);
    o->Maintain();
}

void multi(node *o,int x,int y,long long val){
    if(x<=o->l&&o->r<=y){
        o->sum=o->sum*val%p;
        o->add=o->add*val%p;
        o->mulit=o->mulit*val%p;
        return;
    }
    o->push_down();
    int m=o->l+o->r>>1;
    if(x<=m)multi(o->ls,x,y,val);
    if(m<y) multi(o->rs,x,y,val);
    o->Maintain();
}

void Update(node *o,int x,int y,long long val){
    if(x<=o->l&&o->r<=y){
        o->sum=(o->sum+val*(o->r-o->l+1))%p;
        o->add=(o->add+val)%p;
        return;
    }
    o->push_down();
    int m=o->l+o->r>>1;
    if(x<=m)Update(o->ls,x,y,val);
    if(m<y) Update(o->rs,x,y,val);
    o->Maintain();
}

long long Query(node *o,int l,int r){
    if(l<=o->l&&o->r<=r)return o->sum;
    long long ans = 0;
    int m=o->l+o->r>>1;
    o->push_down();
    if(l<=m)ans=(ans+Query(o->ls,l,r))%p;
    if(m<r)ans=(ans+Query(o->rs,l,r))%p;
    return ans;
}

void Multi(){
    int l=read<int>(),r=read<int>();
    long long val=read<long long>()%p;
    multi(root,l,r,val);
}

void Add(){
    int l=read<int>(),r=read<int>();
    long long val=read<long long>()%p;
    Update(root,l,r,val);
}

void Ask(){
    int l=read<int>(),r=read<int>();
    printf("%lld\n",Query(root,l,r));
}

int main(){
    freopen("seqb.in","r",stdin);
    freopen("seqb.out","w",stdout);
    n=read<int>();p=read<long long>();
    build(root,1,n);
    int op=read<int>();
    while(op--){
        int ppp=read<int>();
        switch(ppp){
            case 1:Multi();break;
            case 2:Add();break;
            case 3:Ask();break;
        }
    }
}