#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define int long long
int n,t,p,tree[4000005],lazy[4000005],tlazy[4000005];
void build(int id,int l,int r){
	tlazy[id]=1;
	if(l == r){
		scanf("%lld",&tree[id]);
		tree[id]%=p;
		return ;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build((id<<1)+1,mid+1,r);
	tree[id]=tree[id<<1]+tree[(id<<1)+1];
	tree[id]%=p;
	return ;
}
void push_down(int id,int l,int r){
	if(lazy[id]==0&&tlazy[id]==1)return ;
	int mid=(l+r)>>1;
	//////lson
	tree[id<<1]=(tree[id<<1]*tlazy[id]%p+lazy[id]*(mid-l+1)%p)%p; 
	tlazy[id<<1]=(tlazy[id<<1]*tlazy[id])%p;
	lazy[id<<1]=(lazy[id<<1]+lazy[id])%p;
	//////rson
	tree[(id<<1)+1]=(tree[(id<<1)+1]*tlazy[id]%p+lazy[id]*(r-mid)%p)%p; 
	tlazy[(id<<1)+1]=(tlazy[(id<<1)+1]*tlazy[id])%p;
	lazy[(id<<1)+1]=(lazy[(id<<1)+1]+lazy[id])%p;
	lazy[id]=0;
	tlazy[id]=1;
}
void modify(int id,int l,int r,int x,int y,int change){
	if(r<x||l>y)return ;
	if(x<=l&&r<=y){
		lazy[id]=(lazy[id]+change)%p;
		tree[id]=(tree[id]+(r-l+1)*change%p)%p;
		return ; 
	} 
	int mid=(l+r)>>1;
	push_down(id,l,r);
	modify(id<<1,l,mid,x,y,change);
	modify((id<<1)+1,mid+1,r,x,y,change);
	tree[id]=(tree[id<<1]+tree[(id<<1)+1])%p;
}
int find(int id,int l,int r,int x,int y){
	if(y<l||r<x)return 0;
	
	if(x<=l&&r<=y){
		return tree[id];
	}
	int mid=(l+r)>>1;
	push_down(id,l,r);
	int lson=find(id<<1,l,mid,x,y);
	int rson=find((id<<1)+1,mid+1,r,x,y);
	return (lson+rson)%p;
}
void t_modify(int id,int l,int r,int x,int y,int change){
	if(r<x||l>y)return ;
	if(x<=l&&r<=y){
		tlazy[id]=(tlazy[id]*change)%p;
		tree[id]=(tree[id]*change)%p;
		lazy[id]=(lazy[id]*change)%p;
		return ; 
	} 
	int mid=(l+r)>>1;
	push_down(id,l,r);
	t_modify(id<<1,l,mid,x,y,change);
	t_modify((id<<1)+1,mid+1,r,x,y,change);
	tree[id]=(tree[id<<1]+tree[(id<<1)+1])%p;
}
void _init(){
	scanf("%lld%lld",&n,&p);
	
	return ;
}
void Ask(){
	scanf("%lld",&t);
	int s;
	int x,y,z;
	for(int i=1;i<=t;i++){
		scanf("%lld",&s);
		if(s==1){
			scanf("%lld%lld%lld",&x,&y,&z);
			t_modify(1,1,n,x,y,z);
		}
		else if(s == 2){
			scanf("%lld%lld%lld",&x,&y,&z);
			modify(1,1,n,x,y,z);
			
		}
		else{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",find(1,1,n,x,y)%p);
			
		}
	}
	return ;
}
signed main(){
	_init();
	build(1,1,n);
	
	Ask();
	return 0;
}