#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p,m,a[100001],op,b,c,k;
ll lt(ll x){return x<<1;}
ll rt(ll x){return x<<1|1;}
struct node{
	ll tag,mal,w,l,r;
}t[400001];
void up(ll x){t[x].w=t[lt(x)].w+t[rt(x)].w;}
void build(ll la,ll ra,ll x){
	t[x].mal=1,t[x].l=la,t[x].r=ra;
	if(t[x].l==t[x].r){
		t[x].w=a[la];
		return;
	}
	ll mid=la+ra>>1;
	build(la,mid,lt(x));
	build(mid+1,ra,rt(x));
	up(x);
}
void f(ll x,ll k,ll h){
	t[x].w=(t[x].w*h)%m;
	t[x].w=(t[x].w+(t[x].r-t[x].l+1)*k)%m;
	t[x].mal=(t[x].mal*h)%m;
	t[x].tag=(t[x].tag*h+k)%m;
}
void down(ll x){
	f(lt(x),t[x].tag,t[x].mal);
	f(rt(x),t[x].tag,t[x].mal);
	t[x].tag=0;
	t[x].mal=1;
}
void fx(ll x,ll k,ll h,ll la,ll ra){
	if(t[x].l>=la&&t[x].r<=ra){
		t[x].w=(t[x].w*h+(t[x].r-t[x].l+1)*k)%m;
		t[x].tag=(t[x].tag*h+k)%m;
		t[x].mal=(t[x].mal*h)%m;
		return;
	}
	down(x);
	ll mid=t[x].l+t[x].r>>1;
	if(la<=mid)fx(lt(x),k,h,la,ra);
	if(ra>mid)fx(rt(x),k,h,la,ra);
	up(x);
}
ll query(ll x,ll la,ll ra){
	if(t[x].l>=la&&t[x].r<=ra)return t[x].w;
	ll res=0;
	down(x);
	ll mid=t[x].l+t[x].r>>1;
	if(la<=mid)res=(res+query(lt(x),la,ra))%m;
	if(ra>mid)res=(res+query(rt(x),la,ra))%m;
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	build(1,n,1);
	cin>>p;
	for(int i=1;i<=p;i++){
		scanf("%d%d%d",&op,&b,&c);
		if(op==1){
			scanf("%d",&k);
			fx(1,0,k,b,c);
		}
		else if(op==2){
			scanf("%d",&k);
			fx(1,k,1,b,c);
		}
		else{
			cout<<query(1,b,c)<<endl;
		}
	}
	return 0;
}