#include<bits/stdc++.h> #include<bits/extc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=4e5+10; int n,q,p,a[maxn]; struct equa{int a,b;equa(){}equa(int _a,int _b){a=_a,b=_b;}}; void exgcd(ll a,ll b,ll &x,ll &y){ if(!b)return x=1,y=0,void(); exgcd(b,a%b,y,x);y-=a/b*x; } equa operator+(equa A,equa B){ if(A.a==-1||B.a==-1)return {-1,-1}; ll a=A.a,b=A.b,c=B.a,d=B.b; ll p=0,q=0; if((b-d)%__gcd(a,c))return {-1,-1}; exgcd(a,c,p,q); ll L=(d-b)/__gcd(a,c);p*=L; ll now=a*p+b,M=a*c/__gcd(a,c);now=(now%M+M)%M; return {M,now}; } vector<pair<int,equa> >r[maxn]; int z[maxn]; equa get(int a,int b){ a=(a%p+p)%p,b=(b%p+p)%p; if(b%__gcd(a,p))return {-1,-1}; ll x=0,y=0;exgcd(a,p,x,y); ll d=b/__gcd(a,p);x*=d; int md=p/__gcd(a,p);x=(x%md+md)%md; return {md,x}; } void mnc(){ int mx=0; up(i,1,n){ if(i<mx+z[mx]){ z[i]=min(z[2*mx-i],mx+z[mx]-i);r[i]=r[2*mx-i]; if(z[i]&&(~a[i-z[i]]))z[i]--; if(r[i].back().p1>z[i]){ equa tmp; while(r[i].size()&&r[i].back().p1>z[i]) tmp=r[i].back().p2,r[i].pop_back(); if(r[i].size()&&r[i].back().p1==z[i]); else r[i].eb(z[i],tmp); } } else z[i]=0,r[i].eb(0,equa(1,0)); while(1){ z[i]++;int x=i-z[i]+1,y=i+z[i]-1; if(x<1||y>n){z[i]--;break;} else if(x-1<1||y+1>n){r[i].back().p1=z[i];break;} else if(~a[x]){r[i].back().p1=z[i];continue;} else { equa now=r[i].back().p2+get(a[x-1]-a[x+1],a[y+1]-a[y-1]); now=now+get(a[y+1]-a[y-1],a[x-1]-a[x+1]); if(!(~now.a))break; if(now.a!=r[i].back().p2.a) r[i].eb(z[i],now); else r[i].back().p1=z[i]; } } if(i+z[i]>mx+z[mx])mx=i; } } __gnu_pbds::gp_hash_table<int,ll>mp[maxn],mp2[maxn]; int qr(int l,int r){ l+=l&1,r-=r&1; if(l>r)return 0; return (r-l)/2+1; } void slv(){ n=read()*2+1,q=read(),p=read();up(i,1,n)a[i]=-1; for(int i=2;i<=n;i+=2)a[i]=read();mnc(); vector<int>fac; for(int i=1;i*i<=p;++i)if(!(p%i))fac.eb(i),fac.eb(p/i); sort(fac.begin(),fac.end()); fac.erase(unique(fac.begin(),fac.end()),fac.end()); auto rk=[&](int x){return lower_bound(fac.begin(),fac.end(),x)-fac.begin();}; up(i,1,n){ int lst=0; for(auto [x,y]:r[i]){ int cnt=qr(i-x+1,i-lst); mp[rk(y.a)][y.b]+=cnt; int l=i-x+1;l+=l&1;int r=2*i-l; int u=a[l],v=a[r]; int val=(v+(p-u)*1llu*y.b)%p; int g=__gcd(p/y.a,u); mp2[rk(y.a*g)][val%(y.a*g)]+=cnt*1ll*g; lst=x; } } while(q--){ int op=read(),x=read(); if(op==1){ ll res=0; up(i,0,(int)fac.size()-1) if(mp[i].find(x%fac[i])!=mp[i].end()) res+=mp[i][x%fac[i]]; printf("%lld\n",res); } else{ ll res=0; up(i,0,(int)fac.size()-1) if(mp2[i].find(x%fac[i])!=mp2[i].end()) res+=mp2[i][x%fac[i]]; printf("%lld\n",res); } } } int main(){ //freopen("whiteqwq.in","r",stdin),freopen("whiteqwq.out","w",stdout); slv(); return 0; }