#include<bits/stdc++.h>
using namespace std;
#define re register
#define int long long
#define pii pair<int,int>
const int N=1e6+5,inf=1<<27;

int n,mod,q;

int a[N];

struct node{
	int l,r,sum;
	int add,time;
}tr[N<<4];

inline void build(int l,int r,int x){
	tr[x]={l,r,0,0,1};
	if(l==r){
		tr[x].sum=a[l];
		return ;
	}
	
	int mid=l+r>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
}

inline void lazy_down(int x){
	tr[x<<1].sum=(tr[x<<1].sum*tr[x].time+tr[x].add*(tr[x<<1].r-tr[x<<1].l+1))%mod;
	tr[x<<1|1].sum=(tr[x<<1|1].sum*tr[x].time+tr[x].add*(tr[x<<1|1].r-tr[x<<1|1].l+1))%mod;
	
	tr[x<<1].time=(tr[x<<1].time*tr[x].time)%mod;
	tr[x<<1|1].time=(tr[x<<1|1].time*tr[x].time)%mod;
	tr[x<<1].add=(tr[x<<1].add*tr[x].time+tr[x].add)%mod;
	tr[x<<1|1].add=(tr[x<<1|1].add*tr[x].time+tr[x].add)%mod;
	
	tr[x].add=0,tr[x].time=1;
}
inline void update_add(int l,int r,int x,int k){
	if(tr[x].l>r||tr[x].r<l)
		return ;
	if(tr[x].l>=l&&tr[x].r<=r){
		tr[x].sum=(tr[x].sum+k*(tr[x].r-tr[x].l+1))%mod;
		tr[x].add+=k%mod;
		return ;
	}
	
	lazy_down(x);
	update_add(l,r,x<<1,k);
	update_add(l,r,x<<1|1,k);
	tr[x].sum=(tr[x<<1].sum+tr[x<<1|1].sum)%mod;
}
inline void update_time(int l,int r,int x,int k){
	if(tr[x].l>r||tr[x].r<l)
		return ;
	if(tr[x].l>=l&&tr[x].r<=r){
		tr[x].sum=(tr[x].sum*k)%mod;
		tr[x].add*=k,tr[x].time*=k;
		return ;
	}
	
	lazy_down(x);
	update_time(l,r,x<<1,k);
	update_time(l,r,x<<1|1,k);
	tr[x].sum=(tr[x<<1].sum+tr[x<<1|1].sum)%mod;
}

inline int query(int l,int r,int x){
	if(tr[x].l>r||tr[x].r<l)
		return 0;
	if(tr[x].l>=l&&tr[x].r<=r)
		return tr[x].sum;
	
	lazy_down(x);
	return query(l,r,x<<1)+query(l,r,x<<1|1);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>mod;
	for(re int i=1;i<=n;i++)
		cin>>a[i];
	
	build(1,n,1);
	
	cin>>q;
	while(q--){
		int opt;cin>>opt;
		if(opt==1){
			int l,r,time;cin>>l>>r>>time;
			update_time(l,r,1,time);
		}
		else if(opt==2){
			int l,r,add;cin>>l>>r>>add;
			update_add(l,r,1,add);
		}
		else{
			int l,r;cin>>l>>r;
			cout<<query(l,r,1)%mod<<"\n";
		}
	}
	
	return 0;
}