调了一天，心态已经炸了。

#include <bits/stdc++.h>
using namespace std;
long long n,m,d,mod,k,op,l,r,flag=0,a[80000],c[80000],id[80000],s[80000],mi[80000],z[80000],mx,cnt=0;
unordered_map<long long,long long>phi;
long long power(long long a,long long p,long long mod)
{
	long long ans=1,x=a;
	while(p)
	   {
	   	if(p&1)ans=ans*x;
	   	if(ans>=mod)flag=1,ans%=mod;
	   	p>>=1;
	   	x=x*x;
	   	if(x>=mod&&p>0)flag=1,x%=mod;
	   }
	return ans;
}

long long getphi(long long x)
{
    long long ans=x;
    for(long long i=2;i*i<=x;i++)
        if(x%i==0)
           {
           ans=ans/i*(i-1);
           while(x%i==0)x/=i;
           }
    if(x!=1)ans=ans/x*(x-1);
    return ans;
}

long long oula(long long x,long long now,long long dep)
{
	if(now<=0)return 0;
    else if(dep>=c[x])
		   {
		   if(z[x]<now)return z[x];
		   else 
		      {
		      flag=1;
		      return z[x]%now+now;
		      }
	       }
	else return power(d,oula(x,phi[now],dep+1)+phi[now]*flag,now);
}

void modify(long long x)
{
	long long i=x,p=id[x];
	flag=0;
	c[i]++,s[p]-=a[i],a[i]=oula(i,mod,0),s[p]+=a[i],s[p]=(s[p]%mod+mod)%mod;
}

void update()
{
	scanf("%lld%lld",&l,&r);
	long long p=id[l],q=id[r];
	if(p==q)
	   {
	   	mi[p]=99999999;
	   	for(int i=(p-1)*k+1;i<=p*k;i++)
	   	   {
		   if(i>=l&&i<=r)modify(i);
		   mi[p]=min(mi[p],c[i]);
	       }
	    return;
	   }
	for(int i=(p-1)*k+1;i<=p*k;i++)
	    {
	    mi[p]=99999999;
	    if(i>=l)modify(i);
	    mi[p]=min(mi[p],c[i]);
		}
	for(int i=(q-1)*k+1;i<=q*k;i++)
	    {
	    mi[q]=99999999;
	    if(i<=r)modify(i);
	    mi[q]=min(mi[q],c[i]);
		}
	for(int i=p+1;i<=q-1;i++)
	    if(mi[i]>=mx+1)continue;
	    else
	       {
	       	mi[i]=99999999;
	       	for(int j=(i-1)*k+1;j<=i*k;j++)modify(j),mi[i]=min(mi[i],c[j]);
		   }
}

long long query()
{
	scanf("%lld%lld",&l,&r);
	long long ans=0,p=id[l],q=id[r];
	if(p==q)
	   {
	   	for(int i=l;i<=r;i++)ans=(ans+a[i])%mod;
	   	return ans;
	   }
	for(int i=l;i<=p*k;i++)ans=(ans+a[i])%mod;
	for(int i=(q-1)*k+1;i<=r;i++)ans=(ans+a[i])%mod;
	for(int i=p+1;i<=q-1;i++)ans=(ans+s[i])%mod;
	return ans;
}

int main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&mod,&d);
	k=sqrt(n),mx=log2(mod);
	long long zs=mod;
	while(zs!=1)
	    {
	    	phi[zs]=getphi(zs);
	    	zs=phi[zs];
		}
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),z[i]=a[i];
	for(int i=1;i<=n;i++)
	    {
	    	id[i]=(i-1)/k+1;
	    	s[id[i]]+=a[i];
		}
	for(int i=1;i<=m;i++)
	    {
	    	scanf("%lld",&op);
	    	if(op==0)update();
	    	else if(op==1)printf("%lld\n",query());
		}
	return 0;
}