[Ahoi2009]Seq 维护序列seq
Description
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

Input
第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

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

Sample Input
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

Sample Output
2

35

8

HINT
【样例说明】

初始时数列为(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。

const int N=1e5+3;
int n,x,y,z,T,P,op,A[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree
{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    struct QAQ
	{
	     LL S,mul,add;
	}  tr[N<<2];
    inline void pushup(Re p)
	{
	  tr[p].S=(tr[pl].S+tr[pr].S)%P;
	}
    inline void updata1(Re p,LL v)
	{
        tr[p].S=(LL)tr[p].S*v%P,
		tr[p].mul=(LL)tr[p].mul*v%P,
		tr[p].add=(LL)tr[p].add*v%P;
    }
    inline void updata2(Re p,Re L,Re R,LL v)
	{
	     (tr[p].S+=v*(R-L+1)%P)%=P,
		 (tr[p].add+=v)%=P;
	}
    inline void pushdown(Re p,Re L,Re R)
	{
        if(tr[p].mul!=1)
		    updata1(pl,tr[p].mul),
			updata1(pr,tr[p].mul),
			tr[p].mul=1;
        if(tr[p].add)
		   updata2(pl,L,mid,tr[p].add),
		   updata2(pr,mid+1,R,tr[p].add),
		   tr[p].add=0;
    }
    inline void build(Re p,Re L,Re R)
	{
        tr[p].mul=1;
        if(L==R)
		   {
		       tr[p].S=A[L]%P;
			   return;
		   }
        build(pl,L,mid),
		build(pr,mid+1,R);
        pushup(p);
    }
    inline void change(Re p,Re L,Re R,Re l,Re r,Re v,Re op)
	{
        if(l<=L&&R<=r)
		   {if(op<2)
		   //op为1时，乘
		   //op为2时，加 
		       updata1(p,v);
			else 
			    updata2(p,L,R,v);
			return;
		   }
        pushdown(p,L,R);
        if(l<=mid)
		    change(pl,L,mid,l,r,v,op);
        if(r>mid)
		   change(pr,mid+1,R,l,r,v,op);
        pushup(p);
    }
    inline LL ask(Re p,Re L,Re R,Re l,Re r)
	{
        if(l<=L&&R<=r)
		    return tr[p].S;
        LL ans=0;
		pushdown(p,L,R);
        if(l<=mid)
		   (ans+=ask(pl,L,mid,l,r))%=P;
        if(r>mid)
		   (ans+=ask(pr,mid+1,R,l,r))%=P;
        return ans;
    }
}TR;
int main(){
    in(n),in(T),in(P);
    for(Re i=1;i<=n;++i)
	    in(A[i]);
    TR.build(1,1,n);
    while(T--)
	{
        in(op),in(x),in(y);
        if(op<3)
        
		   in(z),TR.change(1,1,n,x,y,z,op);
        else 
		   printf("%lld\n",TR.ask(1,1,n,x,y));
    }
}