#include <bits/stdc++.h>
using namespace std;
const int N=100010;
struct node{
	int l,r;
	int sum,add,mul;
}tr[N*4+10];
int a[N];
int n,p,m;
inline void pushup(int x){
	tr[x].sum=(tr[2*x].sum+tr[2*x+1].sum)%p;
}
inline void eval(int x,int add,int mul){
	tr[x].sum=(tr[x].sum*mul+add*(tr[x].r-tr[x].l+1))%p;
	tr[x].mul=(mul*tr[x].mul)%p;		
	tr[x].add=(tr[x].add*mul+add)%p;
}

inline void pushdown(int x){
	eval(x*2,tr[x].add,tr[x].mul);
	eval(x*2+1,tr[x].add,tr[x].mul);
	tr[x].add=0,tr[x].mul=1;
}
void build(int x,int l,int r){
	tr[x].l=l,tr[x].r=r;
	tr[x].add=0,tr[x].mul=1;
	if(l==r){
		tr[x].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(x*2,l,mid),build(x*2+1,mid+1,r);
	pushup(x);
}
void change(int x,int l,int r,int add,int mul){
	if(l<=tr[x].l&&r>=tr[x].r) eval(x,add,mul);
	else{
		pushdown(x);
		int mid=(l+r)/2;
		if(l<=mid) change(x*2,l,r,add,mul);
		if(r>mid) change(x*2+1,l,r,add,mul);
		pushup(x);
	}
}
int query(int x,int l,int r){
	if(l<=tr[x].l&&r>=tr[x].r) return tr[x].sum;
	pushdown(x);		
	int sum=0;
	int mid=(l+r)/2;
	if(l<=mid) sum=query(x*2,l,r)%p;
	if(r>mid) sum+=query(x*2+1,l,r)%p;
	return sum;
}
int main(){
	int t,g,c,ch;
	cin>>n>>p;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	cin>>m;
	while(m--){
		cin>>ch>>t>>g;
		if(ch==1){
			cin>>c;
			change(1,t,g,0,c);			
		}
		else if(ch==2){
			cin>>c;
			change(1,t,g,c,1);			
		}
		else cout<<query(1,t,g)<<endl;
	}
	return 0;
}