#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;
int n,q,m,f;
ll x,y,k;
ll a[N];
struct node{
	ll x,s;
	ll atag,mtag,l,r;
}tree[N*4];
inline int read(){//快读 
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void build(ll x,ll l,ll r){//建树 
	tree[x].mtag=1;
	tree[x].atag=0;
	tree[x].l=l;
	tree[x].r=r;
	if(l==r){
		tree[x].s=a[l];
		return ;
	}
	ll mid=(l+r)>>1;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	tree[x].s=tree[x*2].s+tree[x*2+1].s;
}
void push_down(ll x){//标记下传
	if(tree[x].mtag!=1){
		tree[x*2].mtag*=tree[x].mtag;
		tree[x*2+1].mtag*=tree[x].mtag;
		tree[x*2].atag*=tree[x].mtag;
		tree[x*2+1].atag*=tree[x].mtag;
		tree[x*2].s*=tree[x].mtag;
		tree[x*2+1].s*=tree[x].mtag;
		tree[x].mtag=1;
	}
	if(tree[x].atag){
		tree[x*2].atag+=tree[x].atag;
		tree[x*2+1].atag+=tree[x].atag;
		tree[x*2].s+=(tree[x*2].r-tree[x*2].l+1)*tree[x].atag;
		tree[x*2+1].s+=(tree[x*2+1].r-tree[x*2+1].l+1)*tree[x].atag;
		tree[x].atag=0;
	}	
}
ll query(ll x,ll l,ll r,ll ql,ll qr){//区间求和 
	if(l>=ql&&r<=qr){
		return tree[x].s;
	}
	push_down(x);
	ll mid=(l+r)>>1;
	if(qr<=mid)return query(x*2,l,mid,ql,qr);
	else if(ql>mid)return query(x*2+1,mid+1,r,ql,qr);
	else return query(x*2,l,mid,ql,mid)+query(x*2+1,mid+1,r,mid+1,qr);
}
void update3(ll x,ll l,ll r,ll ql,ll qr,ll k){//区间修改(加)
	if(l>=ql&&r<=qr){
		tree[x].atag+=k;
		tree[x].s+=(tree[x].r-tree[x].l+1)*k;
		return ;
	}
	push_down(x);
	ll mid=(l+r)>>1;
	if(qr<=mid)update3(x*2,l,mid,ql,qr,k);
	else if(ql>mid)update3(x*2+1,mid+1,r,ql,qr,k);
	else{
		update3(x*2,l,mid,ql,mid,k);
		update3(x*2+1,mid+1,r,mid+1,qr,k);
	}
	tree[x].s=(tree[x*2].s+tree[x*2+1].s)%m;
}
void update4(ll x,ll l,ll r,ll ql,ll qr,ll k){//区间修改(乘)
	if(l>=ql&&r<=qr){
		tree[x].mtag*=k;
		tree[x].s*=k;
		return ;
	}
	push_down(x);
	ll mid=(l+r)>>1;
	if(qr<=mid)update4(x*2,l,mid,ql,qr,k);
	else if(ql>mid)update4(x*2+1,mid+1,r,ql,qr,k);
	else{
		update4(x*2,l,mid,ql,mid,k);
		update4(x*2+1,mid+1,r,mid+1,qr,k);
	}
	tree[x].s=(tree[x*2].s+tree[x*2+1].s)%m;
}
int main(){
	n=read();
	q=read();
	m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		f=read();
		x=read();
		y=read();
		if(f==1){
			k=read();
			update4(1,1,n,x,y,k);
		}else if(f==2){
			k=read();
			update3(1,1,n,x,y,k);
		}else{
			write(query(1,1,n,x,y));
			printf("\n");
		}
	}
	return 0;
}