记录编号	608001	评测结果	AAAAAAAAAA
题目名称	2511.学姐的巧克力盒	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	7.916 s
提交时间	2025-10-22 12:24:01	内存使用	22.07 MiB

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int mod[2],n,m,k,a[N],p;
void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	x*=f;return;
}
struct node{
	ll sum[2][N<<2];
	#define ls (p<<1)
	#define rs (p<<1|1)
	void pushup(int p){
		sum[0][p]=sum[0][ls]*sum[0][rs]%mod[0];
		sum[1][p]=sum[1][ls]*sum[1][rs]%mod[1];
	}
	void build(int p,int l,int r){
		if(l==r){
			sum[0][p]=sum[1][p]=a[l];
		}else{
			int mid=(l+r)>>1;
			build(ls,l,mid);
			build(rs,mid+1,r);
			pushup(p); 
		}
	}
	ll query(int p,int l,int r,int L,int R,int o){
		if(L<=l&&r<=R){
			return sum[o][p];
		}else{
			int mid=(l+r)>>1;ll cnt=1;
			if(L<=mid)cnt=cnt*query(ls,l,mid,L,R,o)%mod[o];
			if(R>mid)cnt=cnt*query(rs,mid+1,r,L,R,o)%mod[o];
			return cnt;
		}
	}
}tr;
int varphi(int n){
	int ans=n;
	for(int i=2;i*i<=n;i++)
	if(n%i==0){
		ans=ans/i*(i-1);
		while(n%i==0)n/=i;
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
}
ll ksm(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=(ans*a)%p;
		a=(a*a)%p;
		b>>=1;
	}
	return ans;
}
int main(){
	freopen("chocolatebox.in","r",stdin);
	freopen("chocolatebox.out","w",stdout);
	read(n),read(m),read(k),read(mod[0]),read(p);
	if(p)mod[1]=varphi(p);
	else mod[1]=mod[0];
	if(!mod[0])mod[0]++; 
	for(int i=1;i<=n;i++)read(a[i]);
	tr.build(1,1,n);
	int o,l,r;
	while(m--){
		read(o),read(l),read(r);
		if(o==1)printf("%lld\n",tr.query(1,1,n,l,r,0));
		else printf("%lld\n",ksm(k,tr.query(1,1,n,l,r,1)));
	}
	return 0;
}