#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,mod,a[114514];
struct node{
    int l,r,sum,mul;
}tree[114514<<2];
int lazy[114514<<2];
void build(int p,int l,int r){
    tree[p].l=l; tree[p].r=r;
    tree[p].sum=0; tree[p].mul=1; lazy[p]=0;
    if(l==r){
    	tree[p].sum=a[l]%mod;
    	return ;
	}
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tree[p].sum=(tree[p<<1].sum+tree[p<<1|1].sum)%mod;
    return ;
}
void pushdown(int p){
    if(lazy[p]){
        tree[p<<1].sum=(tree[p<<1].sum*tree[p].mul%mod+(tree[p<<1].r-tree[p<<1].l+1)%mod*lazy[p]%mod)%mod;
        tree[p<<1|1].sum=(tree[p<<1|1].sum*tree[p].mul%mod+(tree[p<<1|1].r-tree[p<<1|1].l+1)%mod*lazy[p]%mod)%mod;
        tree[p<<1].mul=(tree[p<<1].mul*tree[p].mul)%mod;
        tree[p<<1|1].mul=(tree[p<<1|1].mul*tree[p].mul)%mod;
		lazy[p<<1]=(tree[p<<1].mul*tree[p].mul%mod+lazy[p])%mod; 
		lazy[p<<1|1]=(tree[p<<1|1].mul*tree[p].mul%mod+lazy[p])%mod; 
		lazy[p]=0; tree[p].mul=1;
    }
    return ;
}
void mul_update(int p,int l,int r,int val){
    if(l<=tree[p].l&&tree[p].r<=r){
        tree[p].sum=(tree[p].sum%mod*val)%mod;
        tree[p].mul=(tree[p].mul%mod*val)%mod;
        lazy[p]=(lazy[p]%mod*val)%mod;
        return ;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) mul_update(p<<1,l,r,val);
    if(r>mid) mul_update(p<<1|1,l,r,val);
    tree[p].sum=(tree[p<<1].sum+tree[p<<1|1].sum)%mod;
    return ; 
}
void add_update(int p,int l,int r,int val){
    if(l<=tree[p].l&&tree[p].r<=r){
        tree[p].sum=(tree[p].sum+(tree[p].r-tree[p].l+1)%mod*val%mod)%mod;
        lazy[p]=(lazy[p]+val)%mod;
        return ;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) add_update(p<<1,l,r,val);
    if(r>mid) add_update(p<<1|1,l,r,val);
    tree[p].sum=(tree[p<<1].sum+tree[p<<1|1].sum)%mod;
    return ; 
}
int query(int p,int l,int r){
    if(l<=tree[p].l&&tree[p].r<=r) return tree[p].sum%mod;
    pushdown(p);
    int sum=0,mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) sum+=query(p<<1,l,r);
    if(r>mid) sum+=query(p<<1|1,l,r);
    return sum%mod;
}
signed main(){
    cin>>n>>mod;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    cin>>q;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            mul_update(1,l,r,x);
        }
        else if(op==2){
            int l,r,x;
            cin>>l>>r>>x;
            add_update(1,l,r,x);
        }
        else{
        	int l,r;
        	cin>>l>>r;
        	cout<<query(1,l,r)%mod<<endl;
		}
    }
    return 0;
}