#include<bits/stdc++.h>
using namespace std;
const int N=400005;
class SegmentTree{
	private:
		int d[N],tag1[N],tag2[N],cnt,ls[N],rs[N],q;
		inline void pushup(int &p) {
			d[p]=(d[ls[p]]%q+d[rs[p]]%q)%q;
			d[p]%=q;
		}
		inline void pushdown(int s,int t,int m,int p){
			if(!ls[p]) ls[p]=++cnt;
			if(!rs[p]) rs[p]=++cnt;
			if(tag2[p]!=1){
				tag2[ls[p]]*=tag2[p]%q,tag2[rs[p]]*=tag2[p]%q;
				tag2[ls[p]]%=q,tag2[rs[p]]%=q;
				tag1[ls[p]]*=tag2[p]%q,tag1[rs[p]]*=tag2[p]%q;
				tag1[ls[p]]%=q,tag1[rs[p]]%=q;
				d[ls[p]]*=tag2[p]%q,d[rs[p]]*=tag2[p]%q;
				d[ls[p]]%=q,d[rs[p]]%=q; 
				tag2[p]=1;
			}
			if(tag1[p]){
				tag1[ls[p]]+=tag1[p]%q,tag1[rs[p]]+=tag1[p]%q;
				tag1[ls[p]]%=q,tag1[rs[p]]%=q;
				d[ls[p]]+=tag1[p]%q*((m-s+1)%q)%q,d[rs[p]]+=tag1[p]%q*((t-m)%q)%q;
				d[ls[p]]%=q,d[rs[p]]%=q;
				tag1[p]=0;
			}
		}
		int query(int l,int r,int s,int t,int p){
			if(!p)return 0;
			if(l<=s&&t<=r)return d[p]%q;
			int mid=s+((t-s)>>1),S=0;
			pushdown(s,t,mid,p);
			if(l<=mid){
				S+=query(l,r,s,mid,ls[p]);
				S%=q;
			}
			if(r>mid){
				S+=query(l,r,mid+1,t,rs[p]);
				S%=q;
			}
			return S;
		}
		void add(int l,int r,int c,int s,int t,int &p){
			if(!p) p=++cnt;
			if(l<=s&&t<=r){
				d[p]+=(t-s+1)*c%q,d[p]%=q;
				tag1[p]+=c%q,tag1[p]%=q;
				return ;
			}
			int mid=s+((t-s)>>1);
			pushdown(s,t,mid,p);
			if(l<=mid)add(l,r,c,s,mid,ls[p]);
			if(r>mid)add(l,r,c,mid+1,t,rs[p]);
			pushup(p);
		}
		void mul(int l,int r,int c,int s,int t,int &p){
			if(!p)p=++cnt;
			if(l<=s&&t<=r){
				d[p]*=c%q,d[p]%=q;
				tag2[p]*=c%q,tag1[p]*=c%q;
				tag2[p]%=q,tag1[p]%=q;
				return ;
			}
			int mid=s+((t-s)>>1);
			if(tag1[p]||tag2[p]) pushdown(s,t,mid,p);
			if(l<=mid) mul(l,r,c,s,mid,ls[p]);
			if(r>mid) mul(l,r,c,mid+1,t,rs[p]);
			pushup(p);
		}
	public:
		SegmentTree(){
			cnt=1;
			for(int i=1;i<N;i++) tag2[i]=1;
		}
		inline void fun(int n,int m){
			scanf("%d%d",&n,&q);
			for(int i=1;i<=n;i++){
				int tmp=1,x;
				scanf("%d",&x);
				add(i,i,x,1,n,tmp);
			}
			cin>>m;
			for(int i=1;i<=m;i++){
				int op;
				scanf("%d",&op);
				if(op==2){
					int x,y,z,tmp=1;
					scanf("%d%d%d",&x,&y,&z);
					add(x,y,z,1,n,tmp);
				}else if(op==1){
					int x,y,z,tmp=1;
					scanf("%d%d%d",&x,&y,&z);
					mul(x,y,z,1,n,tmp);	
				}else{
					int x,y;
					scanf("%d%d",&x,&y);
					cout<<query(x,y,1,n,1)%q<<endl;
				}
			}
		}	
}st;
int n,m;
signed main(){
	st.fun(n,m);
	return 0;
}