#include<bits/stdc++.h> #define N 400005 #define ls (k<<1) #define rs (k<<1|1) #define mid (l+r>>1) using namespace std; int n,m,p,c[N],cnt[N<<2][35]; int tmp[35],add[N<<2],mul[N<<2]; inline void pushup(int k){ for(int t(0);t<p;++t) cnt[k][t]=cnt[ls][t]+cnt[rs][t]; } void Build(int k,int l,int r){ add[k]=0;mul[k]=1; if(l==r){ cnt[k][c[l]]=1; return; } Build(ls,l,mid); Build(rs,mid+1,r); pushup(k); } inline void pushdown(int k){ int a(mul[k]),b(add[k]);add[k]=0;mul[k]=1; for(int t(0);t<p;++t) tmp[t]=cnt[ls][t],cnt[ls][t]=0; for(int t(0);t<p;++t) cnt[ls][(t*a+b)%p]+=tmp[t]; for(int t(0);t<p;++t) tmp[t]=cnt[rs][t],cnt[rs][t]=0; for(int t(0);t<p;++t) cnt[rs][(t*a+b)%p]+=tmp[t]; add[ls]=(add[ls]*a+b)%p; add[rs]=(add[rs]*a+b)%p; mul[ls]=(mul[ls]*a)%p; mul[rs]=(mul[rs]*a)%p; } void Update(int k,int l,int r,int s,int t,int a,int b){ if(l>t||r<s) return; if(s<=l&&r<=t){ for(int t(0);t<p;++t) tmp[t]=cnt[k][t],cnt[k][t]=0; for(int t(0);t<p;++t) cnt[k][(t*a+b)%p]+=tmp[t]; add[k]=(add[k]*a+b)%p; mul[k]=(mul[k]*a)%p; return; } pushdown(k); Update(ls,l,mid,s,t,a,b); Update(rs,mid+1,r,s,t,a,b); pushup(k); } int res[35]; void Query(int k,int l,int r,int s,int t){ if(l>t||r<s) return; if(s<=l&&r<=t){ for(int t(0);t<p;++t) res[t]+=cnt[k][t]; return; } pushdown(k); Query(ls,l,mid,s,t); Query(rs,mid+1,r,s,t); } int main(){ // freopen("book.in","r",stdin); // freopen("book.out","w",stdout); scanf("%d%d%d",&n,&m,&p); for(int i(1);i<=n;++i) scanf("%d",&c[i]); Build(1,1,n); while(m--){ int op,l,r,a,b; scanf("%d",&op); if(op==1){ scanf("%d%d%d%d",&l,&r,&a,&b); Update(1,1,n,l,r,a,b); } else{ scanf("%d%d",&l,&r); int ans(0); for(int t(0);t<p;++t) res[t]=0; Query(1,1,n,l,r); for(int t(0);t<p;++t) ans+=(res[t]>0); printf("%d\n",ans); } } return 0; }