#include <cstdio>
#define Rep(i,n) for (int i=1; i<=n; i++)
#define MAXN 100010
#define LL long long
struct segment {
int left,right,mid,lc,rc;
long long mult,add,sum;
} tree[3*MAXN];
int n,M,mod,a[MAXN],tot=1;
int Max(int A,int B) {return A>B?A:B;}
int Min(int A,int B) {return A<B?A:B;}
void Build(int l,int r,int node)
{
tree[node].left=l;
tree[node].right=r;
tree[node].mid=(l+r)/2;
tree[node].mult=1;
tree[node].add=0;
if (l==r) {tree[node].sum=a[r]; return;}
else tree[node].sum=0;
if (l<=tree[node].mid)
{
tot++;
tree[node].lc=tot;
Build(l,tree[node].mid,tot);
tree[node].sum+=tree[tree[node].lc].sum;
tree[node].sum=tree[node].sum%mod;
}
if (tree[node].mid<r)
{
tot++;
tree[node].rc=tot;
Build(tree[node].mid+1,r,tot);
tree[node].sum+=tree[tree[node].rc].sum;
tree[node].sum=tree[node].sum%mod;
}
}
void SegMult(int l,int r,LL delta,int node)
{
if (l>r) return;
if (tree[node].left==l&&tree[node].right==r)
{
tree[node].add=tree[node].add*delta;
tree[node].add%=mod;
tree[node].mult=tree[node].mult*delta;
tree[node].mult%=mod;
}
else {
int ch1,ch2;
ch1=tree[node].lc;
ch2=tree[node].rc;
tree[ch1].mult=tree[ch1].mult*tree[node].mult;
tree[ch1].add=tree[ch1].add*tree[node].mult+tree[node].add;
tree[ch2].mult=tree[ch2].mult*tree[node].mult;
tree[ch2].add=tree[ch2].add*tree[node].mult+tree[node].add;
tree[ch1].mult%=mod;
tree[ch1].add%=mod;
tree[ch2].mult%=mod;
tree[ch2].add%=mod;
tree[node].mult=1; tree[node].add=0;
SegMult(l,Min(tree[node].mid,r),delta,tree[node].lc);
SegMult(Max(tree[node].mid+1,l),r,delta,tree[node].rc);
tree[node].sum=(tree[ch1].sum*tree[ch1].mult+tree[ch1].add*(tree[ch1].right-tree[ch1].left+1))
+(tree[ch2].sum*tree[ch2].mult+tree[ch2].add*(tree[ch2].right-tree[ch2].left+1));
tree[node].sum=tree[node].sum%mod;
}
}
void SegAdd(int l,int r,LL delta,int node)
{
if (l>r) return;
tree[node].mult=tree[node].mult%mod;
tree[node].add=tree[node].add%mod;
if (tree[node].left==l&&tree[node].right==r)
{
tree[node].add=tree[node].add+delta;
}
else {
int ch1,ch2;
ch1=tree[node].lc;
ch2=tree[node].rc;
tree[ch1].mult=tree[ch1].mult*tree[node].mult;
tree[ch1].add=tree[ch1].add*tree[node].mult+tree[node].add;
tree[ch2].mult=tree[ch2].mult*tree[node].mult;
tree[ch2].add=tree[ch2].add*tree[node].mult+tree[node].add;
tree[ch1].mult%=mod;
tree[ch1].add%=mod;
tree[ch2].mult%=mod;
tree[ch2].add%=mod;
tree[node].mult=1; tree[node].add=0;
SegAdd(l,Min(tree[node].mid,r),delta,tree[node].lc);
SegAdd(Max(tree[node].mid+1,l),r,delta,tree[node].rc);
tree[node].sum=(tree[ch1].sum*tree[ch1].mult+tree[ch1].add*(tree[ch1].right-tree[ch1].left+1))
+(tree[ch2].sum*tree[ch2].mult+tree[ch2].add*(tree[ch2].right-tree[ch2].left+1));
tree[node].sum=tree[node].sum%mod;
}
}
LL getsum(int l,int r,int node)
{
if (l>r) return 0;
tree[node].mult=tree[node].mult%mod;
tree[node].add=tree[node].add%mod;
if (tree[node].left==l&&tree[node].right==r)
return (((tree[node].sum%mod)*(tree[node].mult%mod))%mod+(tree[node].add%mod)*((r-l+1)%mod))%mod;
LL s1,s2;
s1=getsum(l,Min(tree[node].mid,r),tree[node].lc)%mod;
s2=getsum(Max(tree[node].mid+1,l),r,tree[node].rc)%mod;
return (((s1+s2)%mod)*(tree[node].mult%mod)+((tree[node].add%mod)*(r-l+1)%mod))%mod;
}
void Debug()
{
printf("-----------------------------------\n");
Rep(i,tot)
{
printf("node #%d\n",i);
printf("left=%d right=%d mid=%d\n",tree[i].left,tree[i].right,tree[i].mid);
printf("sum=%lld mult=%lld add=%lld\n",tree[i].sum,tree[i].mult,tree[i].add);
printf("-----------------------------------\n");
}
}
int main()
{
//freopen("seq.in","r",stdin);
//freopen("seq.out","w",stdout);
scanf("%d%d",&n,&mod);
Rep(i,n) scanf("%d",&a[i]);
Build(1,n,1);
scanf("%d",&M);
Rep(i,M)
{
int type,s,t;
LL delta;
scanf("%d%d%d",&type,&s,&t);
if (type<3) scanf("%lld",&delta);
if (type==1) SegMult(s,t,delta,1);
if (type==2) SegAdd(s,t,delta,1);
if (type==3) printf("%lld\n",getsum(s,t,1));
//if (i==8150) printf("%d %d %d\n",type,s,t);
}
//Debug();
return 0;
}