ls-526互联

//Charlie_
#include<bits/stdc++.h>
#define endl '\n'
#define ls (p<<1)
#define rs (p<<1|1)
#define int long long
using namespace std;
int n,a[1000001],m,P;
struct aa
{
	int l,r,sum,add,add2=1;
}t[4000040];
inline int read()
{
	int x=0;bool f=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar());//if(c=='-')f=0;
	for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);
	return f?x:~x+1;
}
void write(int x)
{
	//if(x<0)putchar('-'),x=~x+1;
	if(x>9)write(x/10);
	putchar((x%10)^48);
}
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r){t[p].sum=a[l];return ;}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	t[p].sum=(t[ls].sum+t[rs].sum)%P;
}
void spread(int p)
{
	if(t[p].add||t[p].add2!=1)
	{
		t[ls].sum=((t[p].add2%P*t[ls].sum%P)%P+t[p].add%P*(t[ls].r-t[ls].l+1)%P)%P;
		t[rs].sum=((t[p].add2%P*t[rs].sum%P)%P+t[p].add%P*(t[rs].r-t[rs].l+1)%P)%P;
		t[ls].add2=(t[ls].add2%P*t[p].add2%P)%P;
		t[rs].add2=(t[rs].add2%P*t[p].add2%P)%P;
		t[ls].add=(t[ls].add%P*t[p].add2+t[p].add)%P;
		t[rs].add=(t[rs].add%P*t[p].add2+t[p].add)%P;
		t[p].add=0;
		t[p].add2=1;
	}
}
int ask(int p,int l,int r)
{
	if(l<=t[p].l&&r>=t[p].r) return t[p].sum%P;
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	int val=0;
	if(l<=mid) val=(val+ask(ls,l,r))%P;
	if(r>mid) val=(val+ask(rs,l,r))%P;
	return val%P;
}
void change1(int p,int l,int r,int d)
{
	if(l<=t[p].l&&r>=t[p].r)
	{
		t[p].sum=t[p].sum%P+(d%P*(t[p].r-t[p].l+1))%P;
		t[p].add+=d;
		t[p].sum%=P;
		t[p].add%=P;
		return ;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) change1(ls,l,r,d);
	if(r>mid) change1(rs,l,r,d);
	t[p].sum=(t[ls].sum+t[rs].sum)%P;
}
void change2(int p,int l,int r,int d)
{
	if(l<=t[p].l&&r>=t[p].r)
	{
		t[p].sum=t[p].sum%P*d%P;
		t[p].add2=t[p].add2%P*d%P;
		t[p].add=t[p].add%P*d%P;
		t[p].sum%=P,t[p].add2%=P,t[p].add%=P;
		return;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) change2(ls,l,r,d);
	if(r>mid) change2(rs,l,r,d);
	t[p].sum=(t[ls].sum+t[rs].sum)%P;
}
signed main()
{
	//ios::sync_with_stdio(0);
	//cin.tie(0),cout.tie(0);
	//cin>>n>>P;
	n=read(),P=read();
	for(int i=1;i<=n;i++)a[i]=read(),a[i]%=P;//cin>>a[i];
	build(1,1,n);
	m=read();//cin>>m;
	for(int i=1;i<=m;i++)
	{
		int s,x,y,z;
		s=read(),x=read(),y=read();//cin>>s>>x>>y;
		if(s==1)
		{
			z=read();//cin>>z;
			change2(1,x,y,z);
		}
		else if(s==2)
		{
			z=read();//cin>>z;
			change1(1,x,y,z);
		}
		else write(ask(1,x,y)%P),puts(" ");//cout<<ask(1,x,y)%P<<endl;
	}
}