感觉线段树开得够大了(40倍),可还是RE（qmq）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,q,mod,a[100010];
ll tree[4000001],tag_add[4000001],tag_mul[4000001];
ll ls(ll p)
{
	return p<<2;
}
ll rs(ll p)
{
	return p<<2|1;
}
void push_up(ll p)
{
	tree[p]=tree[ls(p)]+tree[rs(p)];
	tree[p]%=mod;
}
void build(ll p,ll l,ll r)
{
	if(l==r)
	{
		tree[p]=a[l];
		tree[p]%=mod;
		return ;
	}
	ll mid=(r+l)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
void push_down(ll p,ll l,ll r)
{
	ll mid=(r+l)>>1;
	tree[ls(p)]*=tag_mul[p];
	tree[ls(p)]%=mod;
	tree[rs(p)]*=tag_mul[p];
	tree[rs(p)]%=mod;
	tag_mul[ls(p)]*=tag_mul[p];
	tag_mul[ls(p)]%=mod;
	tag_mul[rs(p)]*=tag_mul[p];
	tag_mul[rs(p)]%=mod;
	//
	tag_add[ls(p)]*=tag_mul[p];
	tag_add[ls(p)]%=mod;
	tag_add[rs(p)]*=tag_mul[p];
	tag_add[rs(p)]%=mod;
	//
	tree[ls(p)]+=tag_add[p]*(mid-l+1);
	tree[ls(p)]%=mod;
	tree[rs(p)]+=tag_add[p]*(r-mid);
	tree[rs(p)]%=mod;
	tag_add[ls(p)]+=tag_add[p];
	tag_add[ls(p)]%=mod;
	tag_add[rs(p)]+=tag_add[p];
	tag_add[rs(p)]%=mod;
	tag_add[p]=0;
	tag_mul[p]=1;
}
void add(ll p,ll l,ll r,ll nl,ll nr,ll k)
{
	if(nl<=l&&r<=nr)
	{
		tree[p]+=k*(r-l+1);
		tree[p]%=mod;
		tag_add[p]+=k;
		tag_add[p]%=mod;
		return ;
	}
	push_down(p,l,r);
	ll mid=(l+r)>>1;
	if(nl<=mid) add(ls(p),l,mid,nl,nr,k);
	if(nr>mid) add(rs(p),mid+1,r,nl,nr,k);
	push_up(p);
}
void mul(ll p,ll l,ll r,ll nl,ll nr,ll k)
{
	if(nl<=l&&r<=nr)
	{
		tree[p]*=k;
		tag_add[p]*=k;
		tag_mul[p]*=k;
		tree[p]%=mod;
		tag_add[p]%=mod;
		tag_mul[p]%=mod;
		return ;
	}
	push_down(p,l,r);
	ll mid=(l+r)>>1;
	if(nl<=mid) mul(ls(p),l,mid,nl,nr,k);
	if(nr>mid) mul(rs(p),mid+1,r,nl,nr,k);
	push_up(p);
}
ll check(ll p,ll l,ll r,ll nl,ll nr)
{
	ll ans=0;
	if(nl<=l&&r<=nr) return tree[p];
	push_down(p,l,r);
	ll mid=(l+r)>>1;
	if(nl<=mid) ans+=check(ls(p),l,mid,nl,nr);
	ans%=mod;
	if(nr>mid) ans+=check(rs(p),mid+1,r,nl,nr);
	ans%=mod;
	return ans;
}
int main()
{
	for(int i=1;i<=400000;i++)
	tag_mul[i]=1;
	scanf("%lld%lld%lld",&n,&q,&mod);
	for(ll i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	build(1,1,n);
	for(ll i=1;i<=q;i++)
	{
		ll c,x,y,k;
		scanf("%lld%lld%lld",&c,&x,&y);
		if(c==2)
		{
			scanf("%lld",&k);
			add(1,1,n,x,y,k);
		}
		else if(c==1)
		{
			scanf("%lld",&k);
			mul(1,1,n,x,y,k);
		}
		else if(c==3) cout<<check(1,1,n,x,y)<<'\n';
	}
	return 0;
 }