#include<bits/stdc++.h> #define ll long long using namespace std; const int MAXN=1e5; ll n,m,mod; ll a[MAXN],c[4*MAXN],add[4*MAXN],mul[4*MAXN]; ll q,x,y,ad,mu; void up(ll p) { c[p]=c[p<<1]|c[p<<1|1]; //cout<<p<<c[p]<<endl; } void build(ll l,ll r,ll p) { mul[p]=1; if(l==r) { c[p]|=1<<a[l]; //cout<<c[p]<<endl; return ; } ll mid=l+r>>1; build(l,mid,p<<1); build(mid+1,r,p<<1|1); up(p); } void f(int l,int r,int p,int fa) { //cout<<l<<r<<" "<<p<<" "<<c[p]<<endl; int tm=c[p]; for(int i=0;i<=mod;i++) { if((c[p]>>i)&1) { int tmp=(i*mul[fa])%mod; c[p]^=1<<i; c[p]|=1<<tmp; } } c[p]=tm; //cout<<" "<<l<<r<<" "<<p<<" "<<c[p]<<endl; for(int i=0;i<=mod;i++) { if((c[p]>>i)&1) { int tmp=(i+add[fa])%mod; tm^=1<<i; tm|=1<<tmp; } } c[p]=tm; //c[p]=(c[p]+(add[fa]*(r-l+1))%mod)%mod; mul[p]=(mul[p]*mul[fa])%mod; add[p]=((add[p]*mul[fa])%mod+add[fa])%mod; } void down(ll l,ll r,ll p) { ll mid=l+r>>1; f(l,mid,p<<1,p); f(mid+1,r,p<<1|1,p); mul[p]=1,add[p]=0; } void update(ll nl,ll nr,ll l,ll r ,ll p,ll k,ll q) { if(nl<=l&&r<=nr) { if(q==1) { //c[p]=(c[p]*k)%mod; int tm=c[p]; for(int i=0;i<=mod;i++) { if((c[p]>>i)&1) { int tmp=(i*k)%mod; tm^=1<<i; tm|=1<<tmp; } } c[p]=tm; add[p]=(add[p]*k)%mod; mul[p]=(mul[p]*k)%mod; } else { // c[p]=(c[p]+(k*(r-l+1))%mod)%mod; // cout<<k<<endl; //cout<<l<<r<<" "<<c[p]<<endl; int tm=c[p]; for(int i=0;i<=mod;i++) { if((c[p]>>i)&1) { int tmp=(i+k)%mod; // cout<<tmp<<i<<endl; tm^=1<<i; tm|=1<<tmp; //cout<<c[p]<<endl; } } c[p]=tm; //cout<<l<<r<<" "<<c[p]<<endl; add[p]+=k; } return ; } down(l,r,p); ll mid=l+r>>1; if(nl<=mid) update(nl,nr,l,mid,p<<1,k,q); if(mid<nr) update(nl,nr,mid+1,r,p<<1|1,k,q); up(p); } ll ans(ll nl,ll nr,ll l,ll r,ll p) { ll res=0; if(nl<=l&&r<=nr) { // cout<<l<<" "<<r<<" "<<c[p]<<endl; return c[p]; } down(l,r,p); ll mid=l+r>>1; if(nl<=mid) res|=ans(nl,nr,l,mid,p<<1); if(mid<nr) res|=ans(nl,nr,mid+1,r,p<<1|1); // cout<<p<<" "<<l<<" "<<r<<" "<<res<<endl; return res; } signed main() { cin>>n>>m>>mod; for(int i=1;i<=n;i++)cin>>a[i]; build(1,n,1); while(m--) { scanf("%lld%lld%lld",&q,&x,&y); if(q==2) { int tmp=ans(x,y,1,n,1); //cout<<tmp<<endl; int cnt=0; while(tmp) { if(tmp&1) cnt++; tmp>>=1; } cout<<cnt<<endl; // printf("%d\n",&cnt); } else { scanf("%lld%lld",&mu,&ad); update(x,y,1,n,1,mu,1); update(x,y,1,n,1,ad,2); } } return 0; }