#include <iostream> #include <cstdio> #include <cmath> using namespace std; const int N = 400005; const int M = 650; bool t[M][31][2],zt[M],ans[31]; int n,k,c[N],posi[N],L[M],sq,lazy1[M],lazy2[M]; int main() { //freopen("book.in","r",stdin); //freopen("book.out","w",stdout); int m,i,j; scanf("%d%d%d",&n,&m,&k); sq = sqrt(n); for(i = 1;i <= n;i++) { posi[i] = (i - 1) / sq + 1; if(posi[i] != posi[i - 1]) L[posi[i]] = i; lazy1[posi[i]] = 1; } L[posi[n] + 1] = n + 1; for(i = 1;i <= n;i++) { scanf("%d",&c[i]); t[posi[i]][c[i]][0] = 1; } while(m--) { int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op == 1) { int a,b; scanf("%d%d",&a,&b); for(i = L[posi[l]];i < L[posi[l] + 1];i++) { if(l <= i&&i <= r) c[i] = (c[i] * lazy1[posi[l]] * a % k + lazy2[posi[l]] * lazy1[posi[l]] * a + b) % k; else c[i] = (c[i] * lazy1[posi[l]] % k + lazy2[posi[l]]) % k; t[posi[l]][c[i]][zt[posi[l]]^1] = 1; } for(i = 0;i < k;i++) t[posi[l]][i][zt[posi[l]]] = 0; zt[posi[l]]^=1; lazy1[posi[l]] = 1; lazy2[posi[l]] = 0; for(i = posi[l] + 1;i < posi[r];i++) { lazy1[i] = lazy1[i] * a % k; lazy2[i] = (lazy2[i] * a % k + b) % k; } for(i = L[posi[r]];i < L[posi[r] + 1];i++) { if(l <= i&&i <= r) c[i] = (c[i] * lazy1[posi[r]] * a % k + lazy2[posi[r]] * lazy1[posi[r]] * a + b) % k; else c[i] = (c[i] * lazy1[posi[r]] % k + lazy2[posi[r]]) % k; t[posi[r]][c[i]][zt[posi[r]]^1] = 1; } for(i = 0;i < k;i++) t[posi[r]][i][zt[posi[r]]] = 0; zt[posi[r]]^=1; lazy1[posi[r]] = 1; lazy2[posi[r]] = 0; } else { int co = 0; for(i = 0;i < k;i++) ans[i] = 0; for(i = L[posi[l]];i < L[posi[l] + 1];i++) { c[i] = (c[i] * lazy1[posi[l]] % k + lazy2[posi[l]]) % k; if(l <= i&&i <= r) ans[c[i]] = 1; } for(i = posi[l] + 1;i < posi[r];i++) for(j = 0;j < k;j++) if(t[i][j][zt[i]]) ans[j] = 1; for(i = L[posi[r]];i < L[posi[r] + 1];i++) { c[i] = (c[i] * lazy1[posi[r]] % k + lazy2[posi[r]]) % k; if(l <= i&&i <= r) ans[c[i]] = 1; } for(i = 0;i < k;i++) if(ans[i]) co++; printf("%d\n",co); } } return 0; }