0分求条

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,q,m,a[100001],t[400001],c[400001],b[400001];
void dfs(ll w,ll l,ll r) {
	c[w]=1;
	if(l==r)t[w]=a[l]%m;
	else {
		ll mid=l+r>>1;
		dfs(w<<1,l,mid);
		dfs(w<<1|1,mid+1,r);
		t[w]=(t[w<<1]+t[w<<1|1])%m;
	}
}
void pushdown(ll w,ll l,ll r) {
	ll mid=l+r>>1;
	t[w<<1]=(t[w<<1]*c[w]+(mid-l+1)*b[w])%m;
	t[w<<1|1]=(t[w<<1|1]*c[w]+(r-mid)*b[w])%m;
	c[w<<1]=c[w<<1]*c[w]%m;
	c[w<<1|1]=c[w<<1|1]*c[w]%m;
	b[w<<1]=(b[w<<1]*c[w]+b[w])%m;
	b[w<<1|1]=(b[w<<1|1]*c[w]+b[w])%m;
	b[w]=0;
	c[w]=1;
	return;
}
void dfs1(ll w,ll l,ll r,ll x,ll y,ll k) {
	if(l>=x&&r<=y) {
		t[w]=t[w]*k%m;
		b[w]=b[w]*k%m;
		c[w]=c[w]*k%m;
		return;
	}
	ll mid=l+r>>1;
	pushdown(w,l,r);
	if(y<=mid)dfs1(w<<1,l,mid,x,y,k);
	else if(x>mid)dfs1(w<<1|1,mid+1,r,x,y,k);
	else {
		dfs1(w<<1,l,mid,x,mid,k);
		dfs1(w<<1|1,mid+1,r,mid+1,y,k);
	}
	t[w]=(t[w<<1]+t[w<<1|1])%m;
}
void dfs2(ll w,ll l,ll r,ll x,ll y,ll k) {
	if(l>=x&&r<=y) {
		t[w]=(t[w]+(r-l+1)*k)%m;
		b[w]=(b[w]+k)%m;
		return;
	}
	ll mid=l+r>>1;
	pushdown(w,l,r);
	if(y<=mid)dfs2(w<<1,l,mid,x,y,k);
	else if(x>mid)dfs2(w<<1|1,mid+1,r,x,y,k);
	else {
		dfs2(w<<1,l,mid,x,mid,k);
		dfs2(w<<1|1,mid+1,r,mid+1,y,k);
	}
	t[w]=(t[w<<1]+t[w<<1|1])%m;
}
ll dfs3(ll w,ll l,ll r,ll x,ll y) {
	if(l>=x&&r<=y)return t[w];
	pushdown(w,l,r);
	ll mid=l+r>>1,sum=0;
	if(y<=mid)(sum+=dfs3(w<<1,l,mid,x,y))%=m;
	else if(x>mid)(sum+=dfs3(w<<1|1,mid+1,r,x,y))%=m;
	else {
		(sum+=dfs3(w<<1,l,mid,x,mid))%=m;
		(sum+=dfs3(w<<1|1,mid+1,r,mid+1,y))%=m;
	}
	return sum;
}
int main() {
//	freopen("a.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)scanf("%d",a+i);
	dfs(1,1,n);
	scanf("%d",&q);
	while(q--) {
		ll c,x,y;
		scanf("%d%d%d",&c,&x,&y);
		if(c==1) {
			ll k;
			scanf("%d",&k);
			dfs1(1,1,n,x,y,k);
		} else if(c==2) {
			ll k;
			scanf("%d",&k);
			dfs2(1,1,n,x,y,k);
		} else printf("%d\n",dfs3(1,1,n,x,y));
	}
	return 0;
}