一直80分。。(8AC2WA)
#include<bits/stdc++.h>
using namespace std;
struct setree{
long long l,r;
long long sum,add1,add2;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add1(x) tree[x].add1
#define add2(x) tree[x].add2
} tree[10000000];
long long a[10000001],n,m,s;
inline int read(){
int x=0,w=1;
char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
void build(int p,int l,int r)
{
l(p)=l;r(p)=r;
add2(p)=1;//乘法标记
if(l==r){ sum(p)=a[l]%s;return ;}
int mid=(l+r)/2;
build(p*2,l,mid);
build (p*2+1,mid+1,r);
sum(p)=(sum(p*2)%s+sum(p*2+1)%s)%s;
}
void spread(int p,int s)
{
if(add2(p)!=1)
{
add2(p*2)=add2(p)%s*add2(p*2)%s;
add2(p*2+1)=add2(p)%s*add2(p*2+1)%s;
add1(p*2)=add2(p)%s*add1(p*2)%s;
add1(p*2+1)=add2(p)%s*add1(p*2+1)%s;
sum(p*2)=add2(p)%s*sum(p*2)%s;
sum(p*2+1)=add2(p)%s*sum(p*2+1)%s;
add2(p)=1;
}
if(add1(p))
{
add1(p*2)=(add1(p*2)%s+add1(p)%s)%s;
add1(p*2+1)=(add1(p*2+1)%s+add1(p)%s)%s;
sum(p*2)=(sum(p*2)%s+add1(p)*(r(p*2)%s-l(p*2)+1%s)%s)%s;
sum(p*2+1)=(sum(p*2+1)%s+add1(p)*(r(p*2+1)%s-l(p*2+1)+1%s)%s)%s;
add1(p)=0;
}
}
void change1(int p,int l,int r,int d,int s)
{
if(l<=l(p)&&r>=r(p))
{
sum(p)=(sum(p)%s+d*(r(p)-l(p)+1)%s)%s;
add1(p)=(add1(p)%s+d%s)%s;
return;
}
spread(p,s);
int mid=(l(p)+r(p))/2;
if(l<=mid)change1(p*2,l,r,d,s);
if(r>mid)change1(p*2+1,l,r,d,s);
sum(p)=(sum(p*2)%s+sum(p*2+1)%s)%s;
}
void change2(int p,int l,int r,int d,int s)
{
if(l<=l(p)&&r>=r(p))
{
sum(p)=(sum(p)*d)%s;
add2(p)=(add2(p)*d)%s;
add1(p)=(add1(p)*d)%s;
return ;
}
spread(p,s);
int mid=(l(p)+r(p))/2;
if(l<=mid)change2(p*2,l,r,d,s);
if(r>mid)change2(p*2+1,l,r,d,s);
sum(p)=(sum(p*2)%s+sum(p*2+1)%s)%s;
}
long long ask(int p,int l,int r,int s)
{
if(l<=l(p)&&r>=r(p))
{
return sum(p);
}
spread(p,s);
int mid=(l(p)+r(p))/2;
long long val=0;
if(l<=mid)val=(val%s+ask(p*2,l,r,s)%s)%s;
if(r>mid)val=(val%s+ask(p*2+1,l,r,s)%s)%s;
return val%s;
}
int main()
{
long long b,c,d,k;
n=read();
s=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
}
build (1,1,n);
m=read();
while(m--)
{
b=read();
if(b==3)
{
c=read();
d=read();
cout<<ask(1,c,d,s)<<'\n';
}
if(b==1)
{
c=read();
d=read();
k=read();
change2(1,c,d,k,s);
}
if(b==2)
{
c=read();
d=read();
k=read();
change1(1,c,d,k,s);
}
}
return 0;
}