#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100005],id[100005],rt1[505],rt2[505],b[505],s[505],mod;
namespace IO{
	const ll SIZE=1<<21;
	static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
    ll qr;
    char qu[55],c;
    bool f;
	#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
	#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
	#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
	#define puts(x) IO::Puts(x)
	template<typename T>
    inline void read(T&x){
    	for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
    	for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15); 
    	x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
        if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
        while(x) qu[++qr]=x%10^48,x/=10;
        while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
    	for(int i=0;s[i];i++)
			putchar(s[i]);
		putchar('\n');
	}
	struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
inline void pushdown(int x){
	ll xid=id[x];
	for(int i=x;id[i]==xid;i++)
		a[i]=(a[i]*rt2[xid]+rt1[xid])%mod;
	for(int i=x-1;id[i]==xid;i--)
		a[i]=(a[i]*rt2[xid]+rt1[xid])%mod;
	rt2[xid]=1,rt1[xid]=0;
}
inline void work(ll l,ll r,ll x){
	ll lid=id[l],rid=id[r];
	if(lid==rid){
		pushdown(l);
		for(int i=l;i<=r;i++)
			b[lid]+=a[i]*x-a[i],a[i]*=x,a[i]%=mod,b[lid]%=mod;
	}else{
		pushdown(l),pushdown(r);
		for(int i=l;id[i]==lid;i++)
			b[lid]+=a[i]*x-a[i],a[i]=a[i]*x,a[i]%=mod,b[lid]%=mod;
		for(int i=r;id[i]==rid;i--)
			b[rid]+=a[i]*x-a[i],a[i]=a[i]*x,a[i]%=mod,b[rid]%=mod;
		for(int i=lid+1;i<rid;i++)
			b[i]*=x,b[i]%=mod,rt1[i]*=x,rt1[i]%=mod,rt2[i]*=x,rt2[i]%=mod;
	}
}
inline void add(ll l,ll r,ll x){
	ll lid=id[l],rid=id[r];
	if(lid==rid){
		pushdown(l);
		for(int i=l;i<=r;i++)
			a[i]+=x,a[i]%=mod,b[lid]+=x,b[lid]%=mod;
	}else{
		pushdown(l),pushdown(r);
		for(int i=l;id[i]==lid;i++)
			a[i]+=x,a[i]%=mod,b[lid]+=x,b[lid]%=mod;
		for(int i=r;id[i]==rid;i--)
			a[i]+=x,a[i]%=mod,b[rid]+=x,b[rid]%=mod;
		for(int i=lid+1;i<rid;i++)
			b[i]+=s[i]*x,b[i]%=mod,rt1[i]+=x,rt1[i]%=mod;
	}
}
inline ll qry(ll l,ll r){
	ll lid=id[l],rid=id[r],ans(0);
	if(lid==rid)
		for(int i=l;i<=r;i++)
			ans+=rt1[lid]+a[i]*rt2[lid]%mod,ans%=mod;
	else{
		for(int i=l;id[i]==lid;i++)
			ans+=rt1[lid]+a[i]*rt2[lid]%mod,ans%=mod;
		for(int i=r;id[i]==rid;i--)
			ans+=rt1[rid]+a[i]*rt2[rid]%mod,ans%=mod;
		for(int i=lid+1;i<rid;i++)
			ans+=b[i],ans%=mod;
	}
	return ans;
}
int main(){
	ll n,m,len(0),p(1);
	read(n),read(mod);
	for(int i=1;i<=n;i++){
		read(a[i]);
		len++;
		b[p]+=a[i],id[i]=p;
		if(len*len>=n)s[p]=len,rt2[p]=1,len=0,p++;
	}
	rt2[p]=1,s[p]=len;
	read(m);
	while(m--){
		ll op,l,r,x;
		read(op);
		if(op==1){
			read(l),read(r),read(x);
			work(l,r,x);
		}
		if(op==2){
		    read(l),read(r),read(x);
			add(l,r,x);
		}
		if(op==3){
			read(l),read(r);
			write(qry(l,r)),putchar(10);
		}
	}
	return 0;
}

#8 #9 过不了