听灌佬多 玄关orzQAQ

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int l,r,w,bj1,bj2;
}a[800001];
int b[100001],md;
int push_up(int p){
	return a[p*2].w+a[p*2+1].w;
}
void build(int p,int l,int r){
	a[p].l=l;
	a[p].r=r;
	if(l==r){
		a[p].bj1=1;
		a[p].w=b[l]%md;
		return;
	}
	int mid=l+r>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	a[p].w=push_up(p);
	a[p].bj1=1;
}
void work(int p,int l,int r,int c){
	if(a[p].l==l&&a[p].r==r){
		if(l!=r){
			a[p].w+=(r-l+1)*a[p].bj2;
			a[p].w%=md;
			a[p*2].bj2=a[p].bj2;
			a[p*2+1].bj2=a[p].bj2;
			a[p].bj2=0;
			a[p].bj1+=c;
		}
		else{
			a[p].w+=a[p].bj2;
			a[p].bj2=0;
			a[p].bj1+=c;
		}
		return;
	}
	int mid=a[p].l+a[p].r>>1; 
	if(l>mid){
		work(p*2+1,l,r,c);
	}
	else if(r<=mid){
		work(p*2,l,r,c);
	}
	else{
		work(p*2+1,mid+1,r,c);
		work(p*2,l,mid,c);
	}
}
void work1(int p,int l,int r,int c){
	if(a[p].l==l&&a[p].r==r){
		if(a[p].bj1!=1&&l!=r){
			a[p].w*=a[p].bj1;
			a[p].w%=md;
			a[p*2].bj1=a[p].bj1;
			a[p*2+1].bj1=a[p].bj1;
			a[p].bj1=1;
			a[p].bj2+=c;
		}
		else{
			a[p].w*=a[p].bj1;
			a[p].bj1=1;
			a[p].bj2=c;
		}
		return;
	}
	int mid=a[p].l+a[p].r>>1; 
	if(l>mid){
		work1(p*2+1,l,r,c);
	}
	else if(r<=mid){
		work1(p*2,l,r,c);
	}
	else{
		work1(p*2+1,mid+1,r,c);
		work1(p*2,l,mid,c);
	}
}
int work3(int p,int l,int r){
	a[p].w+=(r-l+1)*a[p].bj2;
	a[p].w*=a[p].bj1;
	a[2*p].bj2=a[p].bj2;
	a[2*p+1].bj2=a[p].bj2;
	a[p].bj2=0;
	a[2*p].bj1=a[p].bj1;
	a[2*p+1].bj1=a[p].bj1;
	a[p].bj1=1;
	if(l==a[p].l&&r==a[p].r){
		a[p].w%=md;
		return a[p].w;
	}
	int mid=a[p].l+a[p].r>>1;
	if(l>mid){
		return work3(p*2+1,l,r);
	}
	else if(r<=mid){
		return work3(p*2,l,r);
	}
	else{
		return (work3(p*2,l,mid)+work3(p*2+1,mid+1,r))%md;
	}
}
int main(){
	int n;
	scanf("%d%d",&n,&md);
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	build(1,1,n);
	int m;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int op;
		scanf("%d",&op);
		if(op==1){
			int t,g,c;
			scanf("%d%d%d",&t,&g,&c);
			c%=md;
			work(1,t,g,c);
		}
		else if(op==2){
			int t,g,c;
			scanf("%d%d%d",&t,&g,&c);
			work1(1,t,g,c);
		}
		else{
			int t,g;
			scanf("%d%d",&t,&g);
			printf("%d\n",work3(1,t,g)%md);
		}
	}
	return 0;
}