简单的线段树+lazy标记下传。
维护加法和乘法两个标记。注意当标记下传时要先乘后加。
写代码时稍稍注意一点点就不会有大问题。
简单题，细节参见下方C++代码好了：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
#define N 100005
int n,p,m,a[N];
long long sum[4*N],add[4*N],mul[4*N];
void build(int pos,int l,int r)
{
mul[pos]=1;
if(l==r){ scanf("%lld",&sum[pos]); return; }
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
sum[pos]=(sum[lson]+sum[rson])%p;
}
void pushdown(int pos,int l,int r)
{
int mid=(l+r)>>1;
sum[lson]=(sum[lson]*mul[pos]+(mid-l+1)*add[pos])%p;
sum[rson]=(sum[rson]*mul[pos]+(r-mid)*add[pos])%p;
mul[lson]=mul[lson]*mul[pos]%p;
mul[rson]=mul[rson]*mul[pos]%p;
add[lson]=(add[lson]*mul[pos]+add[pos])%p;
add[rson]=(add[rson]*mul[pos]+add[pos])%p;
mul[pos]=1;add[pos]=0;
}
void work(int pos,int l,int r,int x,int y,int u,int v)
{
if(x<=l&&r<=y)
{
sum[pos]=(sum[pos]*u+v*(r-l+1))%p;
mul[pos]=(mul[pos]*u)%p;
add[pos]=(add[pos]*u+v)%p;
return;
}
pushdown(pos,l,r);
int mid=(l+r)>>1;
if(y<=mid)
work(lson,l,mid,x,y,u,v);
else if(x>mid)
work(rson,mid+1,r,x,y,u,v);
else work(lson,l,mid,x,y,u,v),work(rson,mid+1,r,x,y,u,v);
sum[pos]=(sum[lson]+sum[rson])%p;
}
int query(int pos,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
return sum[pos];
pushdown(pos,l,r);
int mid=(l+r)>>1;
if(y<=mid)
return query(lson,l,mid,x,y);
if(x>mid)
return query(rson,mid+1,r,x,y);
return (query(lson,l,mid,x,y)+query(rson,mid+1,r,x,y))%p;
}
int main()
{
cin>>n>>p;
build(1,1,n);
cin>>m;
while(m--)
{
int opt,t,g,c;
scanf("%d",&opt);
if(opt==1)
scanf("%d%d%d",&t,&g,&c),
work(1,1,n,t,g,c,0);
else if(opt==2)
scanf("%d%d%d",&t,&g,&c),
work(1,1,n,t,g,1,c);
else scanf("%d%d",&t,&g),
printf("%d\n",query(1,1,n,t,g));
}
}