分块
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
LL num,len,l[1000],r[1000],pos[100010],p;
LL a[100010],add[1000],mul[1000],sum[1000];
void pushdown(LL x)
{
if(add[pos[x]]!=0||mul[pos[x]]!=1)
{
for(int i=l[pos[x]];i<=r[pos[x]];i++)a[i]=(((a[i]*mul[pos[x]])%p+add[pos[x]])%p)%p;
add[pos[x]]=0,mul[pos[x]]=1;
}
}
void modify(LL x,LL y,LL c,LL d)
{
pushdown(x),pushdown(y);
if(pos[x]==pos[y]||pos[y]-pos[x]==1)
{
for(int i=x;i<=y;i++)a[i]=((a[i]*c%p+d)%p+p)%p;
}
else
{
for(LL i=pos[x]+1;i<=pos[y]-1;i++)sum[i]=(((sum[i]*c%p+(r[i]-l[i]+1)%p*d%p))%p)%p,mul[i]=(mul[i]*c)%p,add[i]=((add[i]*c%p+d)%p)%p;
for(LL i=x;i<=r[pos[x]];i++)sum[pos[i]]=(((sum[pos[i]]+(a[i]*(c-1)%p)%p+d)%p)%p)%p,a[i]=((a[i]*c%p+d)%p)%p;
for(LL i=l[pos[y]];i<=y;i++)sum[pos[i]]=(((sum[pos[i]]+(a[i]*(c-1)%p)%p+d)%p)%p)%p,a[i]=((a[i]*c%p+d)%p)%p;
}
}
LL query(LL x,LL y)
{
LL res=0;
pushdown(x),pushdown(y);
if(pos[x]==pos[y]||pos[y]-pos[x]==1)
{
for(LL i=x;i<=y;i++)res=(res+a[i])%p;
return res;
}
else
{
for(LL i=pos[x]+1;i<=pos[y]-1;i++)res=(res+sum[i])%p;
for(LL i=x;i<=r[pos[x]];i++)res=(res+a[i])%p;
for(LL i=l[pos[y]];i<=y;i++)res=(res+a[i])%p;
return res;
}
}
int main()
{
LL n;
cin>>n>>p;
for(LL i=1;i<=n;i++)cin>>a[i];
len=sqrt(n);
num=ceil(1.0*n/len);
for(LL i=1;i<=num;i++)l[i]=(i-1)*len+1,r[i]=len*i,mul[i]=1,add[i]=0;
r[num]=n;
for(LL i=1;i<=n;i++)pos[i]=(i-1)/len+1,sum[pos[i]]=((sum[pos[i]]+a[i])%p+p)%p;
LL m;
cin>>m;
while(m--)
{
LL op;
cin>>op;
if(op==1)
{
LL x,y;
LL c;
cin>>x>>y>>c;
modify(x,y,c,0);
}
else if(op==2)
{
LL x,y;
LL c;
cin>>x>>y>>c;
modify(x,y,1,c);
}
else
{
LL x,y;
cin>>x>>y;
cout<<query(x,y)<<endl;
}
}
return 0;
}