rt

#include <bits/stdc++.h>
using namespace std;
const int N=100000;
struct node
{
 int add_tag;
 int mul_tag;
 int sum;
}tree[4*N+5];
int x[N+5];
int n,m,p;
void built(int root,int l,int r)
{
 if(l==r)
 {
    tree[root].sum=x[l]%p;
    tree[root].add_tag=0;
    tree[root].mul_tag=1;
    return;
 }
 int mid=(l+r)/2;
 built(root*2,l,mid);
 built(root*2+1,mid+1,r);
 tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
 tree[root].add_tag=0;
 tree[root].mul_tag=1;
 tree[root].sum%=p;
}
void pushdown(int root,int l,int r)
{
 if(tree[root].mul_tag!=1)
 {
    tree[root*2].sum*=tree[root].mul_tag;
    tree[root*2].add_tag*=tree[root].mul_tag;
    tree[root*2].mul_tag*=tree[root].mul_tag;
    tree[root*2].sum%=p;
    tree[root*2].add_tag%=p;
    tree[root*2].mul_tag%=p;
    tree[root*2+1].sum*=tree[root].mul_tag;
    tree[root*2+1].add_tag*=tree[root].mul_tag;
    tree[root*2+1].mul_tag*=tree[root].mul_tag;
    tree[root*2+1].sum%=p;
    tree[root*2+1].add_tag%=p;
    tree[root*2+1].mul_tag%=p;
    tree[root].mul_tag=1;
 }
 if(tree[root].add_tag!=0)
 {
    int mid=(l+r)/2;
    tree[root*2].add_tag+=tree[root].add_tag;
    tree[root*2].sum=tree[root*2].sum+(mid-l+1)*tree[root].add_tag;
    tree[root*2].add_tag%=p;
    tree[root*2].sum%=p;
    tree[root*2+1].add_tag+=tree[root].add_tag;
    tree[root*2+1].sum=tree[root*2+1].sum+(r-mid)*tree[root].add_tag;
    tree[root*2+1].add_tag%=p;
    tree[root*2+1].sum%=p;
    tree[root].add_tag=0;
 }
}
void mul_change(int L,int R,int root,int l,int r,int d)
{
 if(L<=l&&R>=r)
 {
    tree[root].mul_tag=(tree[root].mul_tag*d)%p;
    tree[root].add_tag=(tree[root].add_tag*d)%p;
    tree[root].sum=(tree[root].sum*d)%p;
    return ;
 }
 int mid=(l+r)/2;
 pushdown(root,l,r);
 tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
 tree[root].sum%=p;
 if(L<=mid) mul_change(L,R,root*2,l,mid,d);
 if(R>mid)  mul_change(L,R,root*2+1,mid+1,r,d);
 tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
 tree[root].sum%=p;
}
void add_change(int L,int R,int root,int l,int r,int d)
{
 if(L<=l&&R>=r)
 {
    tree[root].add_tag=tree[root].add_tag+d;
    tree[root].sum+=(r-l+1)*d;
    tree[root].add_tag%=p;
    tree[root].sum%=p;
    return ;
 }
 int mid=(l+r)/2;
 pushdown(root,l,r);
 tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
 tree[root].sum%=p;
 if(L<=mid) add_change(L,R,root*2,l,mid,d);
 if(R>mid)  add_change(L,R,root*2+1,mid+1,r,d);
 tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
 tree[root].sum%=p;
}
int search(int L,int R,int root,int l,int r)
{
 if(L<=l&&R>=r)
    return tree[root].sum;
 pushdown(root,l,r);
 int mid=(l+r)/2,res=0;
 if(L<=mid) res+=search(L,R,root*2,l,mid),res%=p;
 if(R>mid)  res+=search(L,R,root*2+1,mid+1,r),res%=p;
 res%=p;
 return res;
}
int main()
{
 scanf("%d%d",&n,&p);
 for(int i=1;i<=n;i++)
    scanf("%d",&x[i]);
 built(1,1,n);
 scanf("%d",&m);
 while(m--)
 {
    int a1,a2,a3,a4;
    scanf("%d",&a1);
    if(a1==1)
    {
        scanf("%d%d%d",&a2,&a3,&a4);
        mul_change(a2,a3,1,1,n,a4);
    }
    if(a1==2)
    {
        scanf("%d%d%d",&a2,&a3,&a4);
        add_change(a2,a3,1,1,n,a4);
    }
    if(a1==3)
    {
        scanf("%d%d",&a2,&a3);
        printf("%d\n",search(a2,a3,1,1,n));
    }
 }
 return 0;
}