线段树30分求调

#include<cstdio>
long long Mod;
class Tr{
	public:
		long long s,lz,c;
}Tree[100005<<2];
int a[100005];
inline int lc(int u)
{
	return u<<1;
}
inline int rc(int u)
{
	return u<<1|1;
}
inline void Push_up(int u)
{
	Tree[u].s=(Tree[lc(u)].s+Tree[rc(u)].s)%Mod;
	return ;
}
inline void Push_down(int l,int r,int u)
{
//	if(l==r||Tree[u].lz==0)return ;
	Tree[lc(u)].lz=(Tree[lc(u)].lz*Tree[u].c+Tree[u].lz)%Mod;
	Tree[rc(u)].lz=(Tree[rc(u)].lz*Tree[u].c+Tree[u].lz)%Mod;
	Tree[lc(u)].c*=Tree[u].c%=Mod;
	Tree[rc(u)].c*=Tree[u].c%=Mod;
	int m=l+r>>1;
	Tree[lc(u)].s=(Tree[lc(u)].s*Tree[u].c+Tree[u].lz*(m-l+1))%Mod;
	Tree[rc(u)].s=(Tree[rc(u)].s*Tree[u].c+Tree[u].lz*(r-m))%Mod;
	Tree[u].lz=0;Tree[u].c=1;
	return ;
}
inline long long query(int ql,int qr,int l,int r,int u)
{
//	printf("Query:%d %d %d\n",l,r,u);
	if(ql<=l&&qr>=r)return Tree[u].s;
	Push_down(l,r,u);
	int m=l+r>>1;
	long long ans=0;
	if(m>=ql)ans+=query(ql,qr,l,m,lc(u));
	if(m<qr)ans+=query(ql,qr,m+1,r,rc(u));
	return ans%Mod;
}
inline void update(int ql,int qr,int l,int r,int u,long long x)
{
//	printf("Update:%d %d %d\n",l,r,u);
	if(ql<=l&&qr>=r)
	{
		(Tree[u].s+=x*(r-l+1))%=Mod;
		(Tree[u].lz+=x)%=Mod;
		return ;
	}
	Push_down(l,r,u);
	int m=l+r>>1;
	if(m>=ql)update(ql,qr,l,m,lc(u),x);
	if(m<qr)update(ql,qr,m+1,r,rc(u),x);
	Push_up(u);
	return ;
}
inline void _update(int ql,int qr,int l,int r,int u,long long x)
{
	if(ql<=l&&qr>=r)
	{
		Tree[u].s=Tree[u].s*x%Mod;
		Tree[u].c=Tree[u].c*x%Mod;
		Tree[u].lz=Tree[u].lz*x%Mod;
		return ; 
	}
	Push_down(l,r,u);
	int m=l+r>>1;
	if(m>=ql)_update(ql,qr,l,m,lc(u),x);
	if(m<qr)_update(ql,qr,m+1,r,rc(u),x);
	Push_up(u);
	return ;
}
inline void Build(int l,int r,int u)
{
	Tree[u].c=1;
	if(l==r)Tree[u].s=a[l];
	if(l>=r)return ;
	int m=l+r>>1;
	Build(l,m,lc(u));
	Build(m+1,r,rc(u));
	Push_up(u);
	return ;
}
inline void fre()
{
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	return ;
}
int main()
{
//	fre();
	int n,m;
	scanf("%d%d%lld",&n,&m,&Mod);
//	Mod=1145141919810ll;
	for(int i=1;i<=n;++i)
	scanf("%d",&a[i]);
	Build(1,n,1);
	while(m--)
	{
		int x;
		scanf("%d",&x);
		if(x==1)
		{
			int l,r;
			long long k;
			scanf("%d%d%lld",&l,&r,&k);
			_update(l,r,1,n,1,k);
		}
		if(x==2)
		{
			int l,r;
			long long k;
			scanf("%d%d%lld",&l,&r,&k);
			update(l,r,1,n,1,k);
		}
		if(x==3)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			printf("%lld\n",query(l,r,1,n,1));
		}
	}
	return 0;
}