放题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5;
int n,p,m,a[N];
int tree[N],tag_add[N],tag_mul[N];
void lazy(int l,int r,int now,int add,int mul)
{
tree[now]=tree[now]*mul+add*(r-l+1);
tree[now]%=p;
tag_add[now]=tag_add[now]*mul+add;
tag_add[now]%=p;
tag_mul[now]*=mul;
tag_mul[now]%p;
}
void push_up(int now)
{
tree[now]=tree[now*2]+tree[now*2+1];
tree[now]%=p;
}
void push_down(int l,int r,int now)
{
int mid=(l+r)/2;
lazy(l,mid,now*2,tag_add[now],tag_mul[now]);
lazy(mid+1,r,now*2+1,tag_add[now],tag_mul[now]);
tag_add[now]=0;
tag_mul[now]=1;
}
void build(int l,int r,int now)
{
tag_mul[now]=1;
if(l==r)
{
tree[now]=a[l];
return;
}
int mid=(l+r)/2;
build(l,mid,now*2);
build(mid+1,r,now*2+1);
push_up(now);
}
void update_mul(int l,int r,int nl,int nr,int now,int k)
{
if(l>=nl&&r<=nr)
{
tag_mul[now]*=k;
tag_mul[now]%=p;
tag_add[now]*=k;
tag_add[now]%=p;
tree[now]*=k;
tree[now]%=p;
return;
}
push_down(l,r,now);
int mid=(l+r)/2;
if(nl<=mid) update_mul(l,mid,nl,nr,now*2,k);
if(nr>mid) update_mul(mid+1,r,nl,nr,now*2+1,k);
push_up(now);
}
void update_add(int l,int r,int nl,int nr,int now,int k)
{
if(l>=nl&&r<=nr)
{
tag_add[now]+=k;
tag_add[now]%=p;
tree[now]+=(r-l+1)*k;
tree[now]%=p;
return;
}
push_down(l,r,now);
int mid=(l+r)/2;
if(nl<=mid) update_add(l,mid,nl,nr,now*2,k);
if(nr>mid) update_add(mid+1,r,nl,nr,now*2+1,k);
push_up(now);
}
int query(int l,int r,int nl,int nr,int now)
{
int ans=0;
if(l>=nl&&r<=nr) return tree[now];
push_down(l,r,now);
int mid=(l+r)/2;
if(nl<=mid) ans+=query(l,mid,nl,nr,now*2);
if(nr>mid) ans+=query(mid+1,r,nl,nr,now*2+1);
return ans%p;
}
signed main()
{
cin>>n>>p;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
cin>>m;
while(m--)
{
int op,l,r,k;
cin>>op>>l>>r;
if(op!=3) cin>>k;
if(op==1) update_mul(1,n,l,r,1,k);
if(op==2) update_add(1,n,l,r,1,k);
if(op==3) cout<<query(1,n,l,r,1)<<"\n";
}
return 0;
}