#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=571373;
int n,m,mod,a[101000];
struct node{
	int l,r,sum,add,mul=1;
}tree[401000];
void build(int p,int l,int r){
	tree[p].l=l,tree[p].r=r; 
	if (l==r){
		tree[p].sum=a[l];
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void down(int p){
	int d=tree[p].add,c=tree[p].mul;
	tree[p*2].sum=(tree[p*2].sum+d*(tree[p*2].r-tree[p*2].l+1))%N;
	tree[p*2].sum=(tree[p*2].sum*c+d*(tree[p*2].r-tree[p*2].l+1))%N;
	tree[p*2].add=(tree[p*2].add*c+d)%N;
	tree[p*2+1].add=(tree[p*2].add*c+d)%N;
	tree[p*2].mul=(tree[p*2].mul*c)%N;
	tree[p*2+1].mul=(tree[p*2].mul*c)%N;
	tree[p].add=0,tree[p].add=1;
}
void update(int p,int l,int r,int k){
	if (tree[p].l>=l && tree[p].r<=r){
		tree[p].sum+=k*(tree[p].r-tree[p].l+1);
		tree[p].add+=k;
		return;
	}
	down(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if (l<=mid)update(p*2,l,r,k);
	if (r>mid)update(p*2+1,l,r,k);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void upcheng(int p,int l,int r,int k){
	if (tree[p].l>=l && tree[p].r<=r){
		tree[p].sum=(tree[p].sum*k)%N;
		tree[p].add=(tree[p].add*k)%N;
		tree[p].mul=(tree[p].mul*k)%N;
		return;
	}
	down(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if (l<=mid)update(p*2,l,r,k);
	if (r>mid)update(p*2+1,l,r,k);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
int ask(int p,int l,int r){
	if (tree[p].l>=l && tree[p].r<=r){
		return tree[p].sum;
	}
	down(p);
	int mid=(tree[p].l+tree[p].r)/2;
	int ans=0;
	if (l<=mid)ans+=ask(p*2,l,r);
	if (r>mid)ans+=ask(p*2+1,l,r);
	return ans;
}
/*void print(int p){
	for (int i=1;i<=15;i++){
		cout<<tree[i].sum<<" "<<tree[p].add<<" "<<tree[p].mul<<endl;
	}
}*/
signed main(){
	cin>>n>>m>>mod;
	for (int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		int c,l,r;
		cin>>c>>l>>r;
		if (c==1){
			int k;
			cin>>k;
			upcheng(1,l,r,k);
			//print(1);
		}
		else if (c==2){
			int k;
			cin>>k;
			update(1,l,r,k);
			//print(1);
		}
		else{
			cout<<ask(1,l,r)<<endl;
		}
	}
	return 0;
}