这0.08s……求卡常

#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline ll read(){
	ll x=0;
	char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

inline void write(ll x){
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return;
}

const int N=1e5+5;
int n,len,q,m;
ll jtag[505],ctag[505],f[505];
ll a[N];
int id[N],L[N],R[N];

inline void updatej(const int &l ,const int &r ,const ll &x){
	if(id[l]==id[r]){
		for(int i=L[id[l]];i<=R[id[l]];++i){
			f[id[i]]-=a[i];
			a[i]=(a[i]*ctag[id[i]]+jtag[id[i]])%m;
			if(l<=i&&i<=r) a[i]=(a[i]+x)%m;
			f[id[i]]=(f[id[i]]+a[i]+m)%m;
		}
		ctag[id[r]]=1,jtag[id[r]]=0;
		return;
	}
	for(int i=L[id[l]];i<=R[id[l]];++i){
		f[id[i]]-=a[i];
		a[i]=(a[i]*ctag[id[i]]+jtag[id[i]])%m;
		if(i>=l) a[i]=(a[i]+x)%m;
		f[id[i]]=(f[id[i]]+a[i]+m)%m;
	}
	for(int i=L[id[r]];i<=R[id[r]];++i){
		f[id[i]]-=a[i];
		a[i]=(a[i]*ctag[id[i]]+jtag[id[i]])%m;
		if(i<=r) a[i]=(a[i]+x)%m;
		f[id[i]]=(f[id[i]]+a[i]+m)%m;
	}
	ctag[id[l]]=1,jtag[id[l]]=0;
	ctag[id[r]]=1,jtag[id[r]]=0;
	for(int i=id[l]+1;i<=id[r]-1;++i){
		jtag[i]=(jtag[i]+x)%m;
	}
	return;
}

inline void updatec(const int &l ,const int &r ,const ll &x ){
	if(id[l]==id[r]){
		for(int i=L[id[l]];i<=R[id[l]];++i){
			f[id[i]]-=a[i];
			a[i]=(a[i]*ctag[id[i]]+jtag[id[i]])%m;
			if(l<=i&&i<=r) a[i]=(a[i]*x)%m;
			f[id[i]]=(f[id[i]]+a[i]+m)%m;
		}
		ctag[id[r]]=1,jtag[id[r]]=0;
		return;
	}
	for(int i=L[id[l]];i<=R[id[l]];++i){
		f[id[i]]-=a[i];
		a[i]=(a[i]*ctag[id[i]]+jtag[id[i]])%m;
		if(i>=l) a[i]=(a[i]*x)%m;
		f[id[i]]=(f[id[i]]+a[i]+m)%m;
	}
	for(int i=L[id[r]];i<=R[id[r]];++i){
		f[id[i]]-=a[i];
		a[i]=(a[i]*ctag[id[i]]+jtag[id[i]])%m;
		if(i<=r) a[i]=(a[i]*x)%m;
		f[id[i]]=(f[id[i]]+a[i]+m)%m;
	}
	ctag[id[r]]=1,jtag[id[r]]=0;
	ctag[id[l]]=1,jtag[id[l]]=0;
	for(int i=id[l]+1;i<=id[r]-1;++i){
		ctag[i]=(ctag[i]*x)%m;
		jtag[i]=(jtag[i]*x)%m;
	}
	return;
}

inline ll query(const int &l ,const int &r ){
	ll ans=0;
	if(id[l]==id[r]){
		for(int i=l;i<=r;++i){
			ans=(ans+a[i]*ctag[id[i]]+jtag[id[i]])%m;
		}
		return ans;
	}
	for(int i=l;i<=R[id[l]];++i){
		ans=(ans+a[i]*ctag[id[i]]+jtag[id[i]])%m;
	}
	for(int i=L[id[r]];i<=r;i++){
		ans=(ans+a[i]*ctag[id[i]]+jtag[id[i]])%m;
	}
	for(int i=id[l]+1;i<=id[r]-1;++i){
		ans=(ans+f[i]*ctag[i]+jtag[i]*(R[i]-L[i]+1))%m;
	}
	return ans;
}

signed main(){
	n=read(),m=read();
	len=sqrt(n);
	for(int i=1;i<=n;++i){
		a[i]=read();
		id[i]=(i-1)/len+1;
		f[id[i]]+=a[i];
		if(L[id[i]]==0) L[id[i]]=i;
		R[id[i]]=i;
		a[i]%=m,f[id[i]]%=m;
	}
	for(int i=1;i<=id[n];++i){
		ctag[i]=1;
	}
	q=read();
	while(q--){
		int op,l,r;
		ll c;
		op=read(),l=read(),r=read();
		if(op==1) updatec(l,r,read());
		if(op==2) updatej(l,r,read());
		if(op==3) write(query(l,r)),puts("");
	}
	return 0;
}