#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define lt (root<<1)
#define rt (root<<1|1)
using namespace std;
const int N=1e5+6;
int n,q,mod,a[N];
struct Node{
	int sum,add,mul,l,r;
}tree[N<<2];
inline int read(){
	int sum=0,d=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) d=c=='-'?-d:d;
	for(;isdigit(c);c=getchar()) sum=(sum<<3)+(sum<<1)+(c&15);
	return sum*d;
} 
void print(int x,int c){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x/10) print(x/10,2);
	putchar(x%10^48);
	if(c^2) putchar(c?'\n':' ');
}
void pushup(int root){
	tree[root].sum=tree[lt].sum+tree[rt].sum;
}
void pushdown(int root){
	tree[lt].sum=(tree[root].mul*tree[lt].sum%mod+(tree[lt].r-tree[lt].l+1)*tree[root].add%mod)%mod;
	tree[rt].sum=(tree[root].mul*tree[rt].sum%mod+(tree[rt].r-tree[rt].l+1)*tree[root].add%mod)%mod;
	tree[lt].mul=(tree[lt].mul*tree[root].mul)%mod;
	tree[rt].mul=(tree[rt].mul*tree[root].mul)%mod;
	tree[lt].add=(tree[lt].add*tree[root].mul%mod+tree[root].add)%mod;
	tree[rt].add=(tree[rt].add*tree[root].mul%mod+tree[root].add)%mod;
	tree[root].add=0;
	tree[root].mul=1;
}
void build(int root,int l,int r){
	tree[root]={a[l]%mod,0,1,l,r};
	if(l==r) return;
	build(lt,l,mid);
	build(rt,mid+1,r);
	pushup(root);
}
void update_add(int root,int l,int r,int ql,int qr,int add){
	if(l>=ql&&r<=qr){
		tree[root].add=(tree[root].add+add)%mod;
		tree[root].sum=(tree[root].sum+add*(r-l+1))%mod;
		return;
	}
	pushdown(root);
	if(ql<=mid) update_add(lt,l,mid,ql,qr,add);
	if(qr>mid) update_add(rt,mid+1,r,ql,qr,add);
	pushup(root);
}
void update_mul(int root,int l,int r,int ql,int qr,int mul){
	if(l>=ql&&r<=qr){
		tree[root].add=(tree[root].add*mul)%mod;
		tree[root].mul=(tree[root].mul*mul)%mod; 
		tree[root].sum=(tree[root].sum*mul)%mod;
		return;
	}
	pushdown(root);
	if(ql<=mid) update_mul(lt,l,mid,ql,qr,mul);
	if(qr>mid) update_mul(rt,mid+1,r,ql,qr,mul);
	pushup(root);
}
int query_sum(int root,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr) return tree[root].sum;
	pushdown(root);
	int res=0;
	if(ql<=mid) res=(res+query_sum(lt,l,mid,ql,qr))%mod;
	if(qr>mid) res=(res+query_sum(rt,mid+1,r,ql,qr))%mod;
	return res;
}
signed main(){
	n=read();
	mod=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	q=read();
	while(q--){
		int op,x,y,k;
		op=read();
		x=read();
		y=read();
		if(op^3){
			k=read();
			if(op^2) update_mul(1,1,n,x,y,k);
			else update_add(1,1,n,x,y,k);
		}
		else print(query_sum(1,1,n,x,y),1);
	}
}

P3373复制过来的，改了下输入，60分