//维护序列
#include <bits/stdc++.h>
#define int long long  
using namespace std;

struct node
{
	long long sum;
	int lazyc=1;
	int lazya=0;
};

long long n,p,m;
long long num[100020];
node tree[400080];


void show()
{
	for(int i=1;i<=15;i++)
	{
		cout<<tree[i].sum<<"--"<<tree[i].lazya<<"--"<<tree[i].lazyc<<"\t";
		if(i==1||i==3||i==7||i==15)
			cout<<endl;
	}
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		tree[x].sum=num[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
	tree[x].sum=tree[2*x].sum%p+tree[2*x+1].sum%p;
	tree[x].sum%=p;
}

void update(int x,int tl,int tr)
{
	tree[x].sum=tree[x].sum%p*tree[x].lazyc+(tr-tl+1)*tree[x].lazya;  //直接先乘后加就好了
	tree[x].sum%=p;
	tree[2*x].lazyc*=tree[x].lazyc;
	tree[2*x].lazya=tree[x].lazyc*tree[2*x].lazya+tree[x].lazya;
	tree[2*x+1].lazyc*=tree[x].lazyc;
	tree[2*x+1].lazya=tree[x].lazyc*tree[2*x+1].lazya+tree[x].lazya;
	tree[x].lazyc=1;
	tree[x].lazya=0; 
	//加标记也要乘 
	
}

void add(int x,int tl,int tr,int l,int r,int k)
{
	if(tl==l&&tr==r)
	{
		tree[x].lazya+=k;
		return ;
	}
	update(x,tl,tr);
	int mid=(tl+tr)>>1;
	if(r<=mid)
	{
		add(2*x,tl,mid,l,r,k);
	}
	else if(l>mid)
	{
		add(2*x+1,mid+1,tr,l,r,k);
	}
	else
	{
		add(2*x,tl,mid,l,mid,k);
		add(2*x+1,mid+1,tr,mid+1,r,k);
	}
	tree[x].sum=tree[2*x].sum%p*tree[2*x].lazyc+tree[2*x].lazya+tree[2*x+1].sum%p*tree[2*x+1].lazyc+tree[2*x+1].lazya;
	tree[x].sum%=p;
	//要递归着把有关于他的祖先节点都修改了，不然可能修改不到它 
}


void chen(int x,int tl,int tr,int l,int r,int k)
{
	if(tl==l&&tr==r)
	{
		tree[x].lazyc*=k;
		tree[x].lazya*=k;
		return ;
	}
	update(x,tl,tr);
	//如果不恰好包含，就需要下放懒标记 
	int mid=(tl+tr)>>1;
	if(r<=mid)
	{
		chen(2*x,tl,mid,l,r,k); 
	}
	else if(l>mid)
	{
		chen(2*x+1,mid+1,tr,l,r,k);
	}
	else
	{
		chen(2*x,tl,mid,l,mid,k);
		chen(2*x+1,mid+1,tr,mid+1,r,k);
	}
	tree[x].sum=tree[2*x].sum%p*tree[2*x].lazyc+tree[2*x].lazya+tree[2*x+1].sum%p*tree[2*x+1].lazyc+tree[2*x+1].lazya;
	tree[x].sum%=p; 
	//不需要修改别的了 
}

long long query(int x,int tl,int tr,int l,int r)
{
	if(tl==l&&tr==r)
	{
		return tree[x].sum%p*tree[x].lazyc+tree[x].lazya*(tr-tl+1); 
	}
	update(x,tl,tr);
	int mid=(tl+tr)>>1;
	if(r<=mid)
	{
		return query(2*x,tl,mid,l,r)%p;
	}
	else if(l>mid)
	{
		return query(2*x+1,mid+1,tr,l,r)%p;
	}
	else
	{
		return query(2*x,tl,mid,l,mid)%p+query(2*x+1,mid+1,tr,mid+1,r)%p; 
	}
}

signed main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		cin>>num[i];
	}
	build(1,1,n);
//	show();
	cin>>m;
	while(m)
	{
		int op,t,g,c;
		cin>>op;
		if(op==1)  //乘 
		{
			cin>>t>>g>>c;
			chen(1,1,n,t,g,c);
		}
		if(op==2)   //加 
		{
			cin>>t>>g>>c;
			add(1,1,n,t,g,c);
		}
		if(op==3)   //查询 
		{
			cin>>t>>g;
			cout<<query(1,1,n,t,g)%p<<endl;
		} 
		//show();
		m--;
	}
	return 0;
 }