#include<iostream> #include<cstdio> #include<cstring> #include<climits> #include<algorithm> #define elif else if #define ll long long using namespace std; ll read() { ll o=0,w=1;char c=getchar(); while(c>'9'||c<'0') { if(c=='-') w=-1; c=getchar(); } while(c>='0'&&c<='9') { o=o*10+c-'0'; c=getchar(); } return o*w; } const int N=400001,M=400001,K=30; int n,m,k,c[N]; #define lson id*2 #define rson id*2+1 struct node { int cnt[30]; node() { memset(cnt,0,sizeof(cnt)); } void init() { memset(cnt,0,sizeof(cnt)); } }sum[4*N]; ll tag1[4*N],tag2[4*N]; inline void push_up(node &ans,node a,node b) { for(int i=0;i<k;i++) { ans.cnt[i]=a.cnt[i]+b.cnt[i]; } } inline void push_down(int id,int l,int r) { if(l!=r) { int a=tag1[id],b=tag2[id]; node x; for(int i=0;i<k;i++) { x.cnt[(i*a+b)%k]+=sum[lson].cnt[i]; } sum[lson]=x;tag1[lson]=(tag1[lson]*a)%k;tag2[lson]=(tag2[lson]*a+b)%k; x.init(); for(int i=0;i<k;i++) { x.cnt[(i*a+b)%k]+=sum[rson].cnt[i]; } sum[rson]=x;tag1[rson]=(tag1[rson]*a)%k;tag2[rson]=(tag2[rson]*a+b)%k; } tag1[id]=1;tag2[id]=0; } inline void build(int id,int l,int r) { tag1[id]=1; if(l==r) { sum[id].cnt[c[l]]++; return; } int mid=(l+r)/2; build(lson,l,mid); build(rson,mid+1,r); push_up(sum[id],sum[lson],sum[rson]); } inline void update(int id,int l,int r,int L,int R,int a,int b) { if(l>R||r<L) return; if(L<=l&&r<=R) { node x; for(int i=0;i<k;i++) { x.cnt[(i*a+b)%k]+=sum[id].cnt[i]; } sum[id]=x; tag1[id]=(tag1[id]*a)%k; tag2[id]=(tag2[id]*a+b)%k; return; } push_down(id,l,r); int mid=(l+r)/2; update(lson,l,mid,L,R,a,b); update(rson,mid+1,r,L,R,a,b); push_up(sum[id],sum[lson],sum[rson]); } node query(int id,int l,int r,int L,int R) { node ans; if(l>R||r<L) return ans; if(L<=l&&r<=R) return sum[id]; int mid=(l+r)/2; push_down(id,l,r); push_up(ans,query(lson,l,mid,L,R),query(rson,mid+1,r,L,R)); return ans; } int main() { // freopen("book.in","r",stdin); // freopen("book.out","w",stdout); cin>>n>>m>>k; for(int i=1;i<=n;i++) cin>>c[i]; build(1,1,n); for(int i=1;i<=m;i++) { int op,x,y;op=read();x=read();y=read(); if(op==1) { int a,b;a=read();b=read(); update(1,1,n,x,y,a,b); } else { node ans=query(1,1,n,x,y); int tot=0; for(int i=0;i<k;i++) if(ans.cnt[i]) tot++; cout<<tot<<'\n'; } } 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 */