AC #1 #3 #4

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int n,q,m,kr[100001];
struct side_tree{
	int l,r,sum,add,mul;
}tr[800001];
void build_tree(int l,int r,int num){
	tr[num].add=0,tr[num].mul=1;
	tr[num].l=l,tr[num].r=r;
	if(l==r){
		tr[num].sum=kr[l]%m;
		return ;
	}
	int mid=(l+r)>>1;
	build_tree(l,mid,num<<1);
	build_tree(mid+1,r,num<<1|1);
	tr[num].sum=(tr[num<<1].sum+tr[num<<1|1].sum)%m;
}
void rush(int num){
	tr[num<<1].sum=(tr[num].mul*tr[num<<1].sum%m+((tr[num<<1].r-tr[num<<1].l+1)*tr[num].add)%m)%m;
	tr[num<<1|1].sum=(tr[num].mul*tr[num<<1|1].sum%m+((tr[num<<1|1].r-tr[num<<1|1].l+1)*tr[num].add)%m)%m;
	
	tr[num<<1].mul=(tr[num].mul*tr[num<<1].mul)%m;
	tr[num<<1|1].mul=(tr[num].mul*tr[num<<1|1].mul)%m;
	
	tr[num<<1].add=(tr[num<<1].add*tr[num].mul+tr[num].add)%m;
    tr[num<<1|1].add=(tr[num<<1|1].add*tr[num].mul+tr[num].add)%m;
    
    tr[num].mul=1,tr[num].add=0;
}
void change_add(int l,int r,int k,int num){
	int ls=tr[num].l,rs=tr[num].r;
	if(l<=ls&&rs<=r){
		tr[num].sum+=(rs-ls+1)*k;
		tr[num].sum%=m;
		tr[num].add+=k;
		tr[num].add%=m;
		return ;
	}
	rush(num);
	int mid=(ls+rs)>>1;
	if(l<=mid)
		change_add(l,r,k,num<<1);
	if(r>mid)
		change_add(l,r,k,num<<1|1);
	tr[num].sum=(tr[num<<1].sum+tr[num<<1|1].sum)%m;	
}
void change_mul(int l,int r,int k,int num){
	int ls=tr[num].l,rs=tr[num].r;
	if(l<=ls&&rs<=r){
		tr[num].sum*=k;
		tr[num].sum%=m;
		tr[num].add*=k;
		tr[num].add%=m;
		tr[num].mul*=k;
		tr[num].mul%=m;
		return ;
	}
	rush(num);
	int mid=(ls+rs)>>1;
	if(l<=mid)
		change_mul(l,r,k,num<<1);//add->mul wa 1
	if(r>mid)
		change_mul(l,r,k,num<<1|1);
	tr[num].sum=(tr[num<<1].sum+tr[num<<1|1].sum)%m;
}
long long find(int l,int r,int num){
	int ls=tr[num].l,rs=tr[num].r;
	if(l<=ls&&rs<=r){
		return tr[num].sum%m;
	}
	long long ans=0;
	rush(num);
	int mid=(ls+rs)>>1;
	if(l<=mid)
		ans+=find(l,r,num<<1);
	if(r>mid)
		ans+=find(l,r,num<<1|1);
	return ans%m;
}
int main(){
	n=read(),q=read(),m=read();
	for(int i=1;i<=n;i++)
		kr[i]=read();
	build_tree(1,n,1);
	int p,x,y,k;
	while(q--){
		p=read(),x=read(),y=read();
		switch(p){
			case 1:{
				k=read();
				change_mul(x,y,k,1);
				break;
			}
			case 2:{
				k=read();
				change_add(x,y,k,1);
				break;
			}
			case 3:{
				cout<<find(x,y,1)<<endl;
				break;
			}
		}
	}
	return 0;
}