#include<bits/stdc++.h> using namespace std; template<typename T>void in(T &a) { T ans=0; char c=getchar(); for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar())ans=ans*10+c-'0'; a=ans; } struct node{ int v,tag1,tag2,l,r; }; node tr[1600005]; int n,m,k,c[400005]; int popcount(int v,int ans=0){ while(v)ans++,v=v&(v-1); return ans; } void modify(int &v,int a,int b,int t=0){ for(int i=0;i<k;i++)if(v&(1<<i))t|=(1<<((i*a+b)%k)); v=t; } void pushdown(int pos){ tr[pos<<1].tag2=tr[pos<<1].tag2*tr[pos].tag2%k,tr[pos<<1|1].tag2=tr[pos<<1|1].tag2*tr[pos].tag2%k; tr[pos<<1].tag1=(tr[pos<<1].tag1*tr[pos].tag2%k+tr[pos].tag1)%k,tr[pos<<1|1].tag1=(tr[pos<<1|1].tag1*tr[pos].tag2%k+tr[pos].tag1)%k; modify(tr[pos<<1].v,tr[pos].tag2,tr[pos].tag1),modify(tr[pos<<1|1].v,tr[pos].tag2,tr[pos].tag1); tr[pos].tag1=0,tr[pos].tag2=1; } void pushup(int pos){ tr[pos].v=tr[pos<<1].v|tr[pos<<1|1].v; } void build(int pos,int nl,int nr,int a[]){ tr[pos].tag1=0,tr[pos].tag2=1,tr[pos].l=nl,tr[pos].r=nr; if(nl==nr)tr[pos].v=1<<a[nl]; else{ int mid=(nl+nr)>>1; build(pos<<1,nl,mid,a),build(pos<<1|1,mid+1,nr,a),pushup(pos); } } void add(int pos,int nl,int nr,int gl,int gr,int a,int b){ if(gl<=nl&&nr<=gr){ tr[pos].tag2=tr[pos].tag2*a%k,tr[pos].tag1=(tr[pos].tag1*a%k+b)%k; modify(tr[pos].v,a,b); return; } pushdown(pos); int mid=(nl+nr)>>1; if(gl<=mid)add(pos<<1,nl,mid,gl,gr,a,b); if(gr>mid)add(pos<<1|1,mid+1,nr,gl,gr,a,b); pushup(pos); } int query(int pos,int nl,int nr,int gl,int gr){ if(gl<=nl&&nr<=gr)return tr[pos].v; pushdown(pos); int mid=(nl+nr)>>1,ans=0; if(gl<=mid)ans|=query(pos<<1,nl,mid,gl,gr); if(gr>mid)ans|=query(pos<<1|1,mid+1,nr,gl,gr); return ans; } int main(){ in(n),in(m),in(k); for(int i=1;i<=n;i++)in(c[i]); build(1,1,n,c); for(int i=1,opt,l,r,a,b;i<=m;i++){ in(opt),in(l),in(r); if(opt==1)in(a),in(b),add(1,1,n,l,r,a,b); else printf("%d\n",popcount(query(1,1,n,l,r))); } return 0; }