#include<bits/stdc++.h> #define ls (now<<1) #define rs (now<<1|1) #define mid ((L+R)>>1) using namespace std; const int N=4e5+100; int read() { int x=0; char t=getchar(); while(t<'0'||t>'9')t=getchar(); while(t>='0'&&t<='9')x=(x<<3)+(x<<1)+(t^48),t=getchar(); return x; } long long n,m,k,c[N],LL,RR,a,b,opt,ans,tmp; int t[N<<1],aa[N<<1],bb[N<<1]; int build(int L,int R,int now) { aa[now]=1; if(L==R) return t[now]=(1<<c[L]); return t[now]=build(L,mid,ls)|build(mid+1,R,rs); } void pushdown(int now) { // cout<<now<<' '<<aa[now]<<' '<<bb[now]<<' '<<t[now]<<endl; // cout<< if((aa[now]==1&&bb[now]==0)||(!t[now]))return ; int nw=0; for(int i=0;i<k;i++) if(t[now]&(1<<i)) nw|=1<<((1ll*i*aa[now]+bb[now])%k); if(t[ls])aa[ls]=1ll*aa[ls]*aa[now]%k,bb[ls]=(1ll*bb[ls]*aa[now]+bb[now])%k; if(t[rs])aa[rs]=1ll*aa[rs]*aa[now]%k,bb[rs]=(1ll*bb[rs]*aa[now]+bb[now])%k; aa[now]=1,bb[now]=0; t[now]=nw; t[now>>1]=t[(now>>1)<<1]|t[(now>>1)<<1|1]; return ; } void pushup(int now) { t[now]=t[ls]|t[rs]; } void fix(int l,int r,int L,int R,int now,int a,int b) { if(l<=L&&R<=r) { aa[now]=1ll*aa[now]*a%k,bb[now]=(1ll*bb[now]*a+b)%k; // cout<<now<<' '<<aa[now]<<' '<<bb[now]<<' '<<t[now]<<endl; pushdown(now); pushup(now); return ; } pushdown(now); if(l<=mid)fix(l,r,L,mid,ls,a,b); if(r>mid)fix(l,r,mid+1,R,rs,a,b); pushup(now); } int ask(int l,int r,int L,int R,int now) { pushdown(now); int cnt=0; if(l<=L&&R<=r) { cnt|=t[now]; return cnt; } if(l<=mid)cnt|=ask(l,r,L,mid,ls); if(r>mid)cnt|=ask(l,r,mid+1,R,rs); return cnt; } int main() { //freopen("book.in","r",stdin); //freopen("book.out","w",stdout); cin>>n>>m>>k; for(int i=1;i<=n;i++) c[i]=read(); build(1,n,1); while(m--) { opt=read(); if(opt==1) { LL=read(),RR=read(),a=read(),b=read(); fix(LL,RR,1,n,1,a,b); } else { LL=read(),RR=read(); tmp=ask(LL,RR,1,n,1); int cntt=0; for(int i=0;i<k;i++) if(tmp&(1<<i)) cntt++; cout<<cntt<<endl; } } return 0; } /* 10 7 5 2 2 2 3 4 4 2 0 1 0 1 4 8 2 3 1 1 9 4 2 2 7 8 2 2 7 1 6 7 0 3 1 1 4 0 1 2 5 6 13 9 6 1 5 1 0 2 2 4 3 3 0 0 4 4 2 2 4 1 2 4 0 5 1 8 13 2 4 2 1 4 1 3 5 1 1 1 3 6 2 3 1 7 11 0 4 2 1 13 2 5 10 */