此代码在线段树2上可以AC，但在此题中#2，#8，#9，#10号点都RE

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[10000001];
int P;
struct treeNode{
	int l,r;
	long long num,ad,ml;
};
treeNode t[10000001];
void buildTree(int p,int l,int r)
{
	t[p].l=l;
	t[p].r=r;
	t[p].ml=1;
	if(l==r)
	{
		t[p].num=a[l]%P;
		return;
	}
	int mid=(l+r)>>1;
	buildTree(p*2,l,mid);
	buildTree(p*2+1,mid+1,r);
	t[p].num=(t[p*2].num+t[p*2+1].num)%P;
}
void pushDown(int p)
{
	long long add=t[p].ad;
	long long mul=t[p].ml;
	t[p*2].num=(t[p*2].num*mul+add*(t[p*2].r-t[p*2].l+1))%P;
	t[p*2+1].num=(t[p*2+1].num*mul+add*(t[p*2+1].r-t[p*2+1].l+1))%P;
	t[p*2].ml=t[p*2].ml*mul%P;
	t[p*2+1].ml=t[p*2+1].ml*mul%P;
	t[p*2].ad=(t[p*2].ad*mul+add)%P;
	t[p*2+1].ad=(t[p*2+1].ad*mul+add)%P;
	t[p].ad=0;
	t[p].ml=1;
}
void add(int p,int l,int r,int k)
{
	if(l<=t[p].l&&r>=t[p].r)
	{
		t[p].num+=(long long)k*(t[p].r-t[p].l+1);
		t[p].ad+=k;
		t[p].num%=P;
		t[P].ad%=P;
		return;
	}
	pushDown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
	{
		add(p*2,l,r,k);
	}
	if(r>mid)
	{
		add(p*2+1,l,r,k);
	}
	t[p].num=t[p*2].num+t[p*2+1].num;
}
void mul(int p,int l,int r,int k)
{
	if(l<=t[p].l&&r>=t[p].r)
	{
		t[p].num*=k;
		t[p].num%=P;
		t[p].ml*=k;
		t[p].ad*=k;
		return;
	}
	pushDown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
	{
		mul(p*2,l,r,k);
	}
	if(r>mid)
	{
		mul(p*2+1,l,r,k);
	}
	t[p].num=t[p*2].num+t[p*2+1].num;
}
long long getSum(int p,int l,int r)
{
	if(l<=t[p].l&&r>=t[p].r)
	{
		return t[p].num%P;
	}
	pushDown(p);
	int mid=(t[p].l+t[p].r)>>1;
	long long _now=0;
	if(l<=mid)
	{
		_now+=getSum(p*2,l,r);
	}
	if(r>mid)
	{
		_now+=getSum(p*2+1,l,r);
	}
	return _now%P;
}
int main()
{
	cin>>n>>P;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
	}
	buildTree(1,1,n);
	cin>>m;
	for(int i=1;i<=m;++i)
	{
		int op,x,y,z;
		cin>>op;
		if(op==2)
		{
			cin>>x>>y>>z;
			add(1,x,y,z);
		}
		else if(op==1)
		{
			cin>>x>>y>>z;
			mul(1,x,y,z);
		}
		else
		{
			cin>>x>>y;
			cout<<getSum(1,x,y)<<endl;
		}
	}
 }