学步园

#include<cstdio>
#include<iostream>
using namespace std;
struct data{
	int l,r;
	long long sum,mul,add;
}tr[400001];
long long n,p,m,a[100001];
void build(int k,int s,int t){
	tr[k].l=s;tr[k].r=t;tr[k].mul=1;
	if(s==t){
		tr[k].sum=a[s];
		return;
	}
	int mid=(s+t)>>1;
	build(k<<1,s,mid);
	build(k<<1|1,mid+1,t);
	tr[k].sum=(tr[k<<1].sum+tr[k<<1|1].sum)%p;
}
void pushdown(int k)
{
    int t=tr[k].r-tr[k].l+1;
    if(t==1)return;
    long long m=tr[k].mul,a=tr[k].add;tr[k].mul=1;tr[k].add=0;
    tr[k<<1].sum=(tr[k<<1].sum*m+(t-(t>>1))*a)%p;
    tr[k<<1|1].sum=(tr[k<<1|1].sum*m+(t>>1)*a)%p;
    tr[k<<1].add=(tr[k<<1].add*m+a)%p;
    tr[k<<1|1].add=(tr[k<<1|1].add*m+a)%p;
    tr[k<<1].mul=tr[k<<1].mul*m%p;
    tr[k<<1|1].mul=tr[k<<1|1].mul*m%p;
}
void update(int k,int s,int t,long long m,long long a){
	pushdown(k);
	int l=tr[k].l,r=tr[k].r;
	if(l==s&&r==t){
		tr[k].sum=(tr[k].sum*m+(r-l+1)*a)%p;
		tr[k].add=(tr[k].add+a)%p;
		tr[k].mul=tr[k].mul*m%p;
		return;
	}
	int mid=(l+r)>>1;
	if(t<=mid)update(k<<1,s,t,m,a);
	else if(s>mid)update(k<<1|1,s,t,m,a);
	else{
		update(k<<1,s,mid,m,a);
		update(k<<1|1,mid+1,t,m,a);
	}
	tr[k].sum=(tr[k<<1].sum+tr[k<<1|1].sum)%p;
}
long long ask(int k,int s,int t){
	pushdown(k);
	int l=tr[k].l,r=tr[k].r;
	if(l==s&&r==t)return tr[k].sum;
	int mid=(l+r)>>1;
	if(t<=mid)return ask(k<<1,s,t)%p;
	else if(s>mid)return ask(k<<1|1,s,t)%p;
	else return (ask(k<<1,s,mid)+ask(k<<1|1,mid+1,t))%p;
}
int main(){
	scanf("%lld %lld",&n,&p);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,1,n);
	scanf("%lld",&m);
    for(int i=1;i<=m;i++)
    {
        int f,x,y,t;
        scanf("%d",&f);
        switch(f)
        {
        case 1:scanf("%d %d %d",&x,&y,&t);update(1,x,y,t,0);break;
        case 2:scanf("%d %d %d",&x,&y,&t);update(1,x,y,1,t);break;
        case 3:scanf("%d %d",&x,&y);printf("%lld\n",ask(1,x,y)%p);break;
        }
    }
	return 0;
}