记录编号	326620	评测结果	AAAAAATTTT
题目名称	学姐的巧克力盒	最终得分	60
用户昵称	Rapiz	是否通过	未通过
代码语言	C++	运行时间	11.312 s
提交时间	2016-10-21 11:13:10	内存使用	58.62 MiB

#include<cstdio>
#define lch (o<<1)
#define rch ((o<<1)+1)
#define mid ((l+r)>>1)
#define file(x) "chocolatebox."#x
typedef long long ll;
const int MAXN=1e6+10;
int n,m,k,p1,p2,ra[MAXN];
int q1,q2,qt;
struct SEG{
	ll a[MAXN<<2],p;
	ll build(int o,int l,int r){
		if(l==r) return a[o]=ra[l];
		return a[o]=build(lch,l,mid)*build(rch,mid+1,r)%p;
	}
	ll qmult(int o,int l,int r){
		if(q1<=l&&r<=q2) return a[o];
		ll ret=1;
		if(q1<=mid) ret=ret*qmult(lch,l,mid)%p;
		if(q2>=mid+1) ret=ret*qmult(rch,mid+1,r)%p;
		return ret;
	}
	void init(ll ip){
		p=ip;
		build(1,1,n);
	}
}seg[2];
ll qpow(ll f,ll r,ll p){
	ll ret=1;
	f%=p;
	while(r){
		if(r&1) ret=ret*f%p;
		f=f*f%p,r>>=1;
	}
	return ret;
}
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	scanf("%d%d%d%d%d",&n,&m,&k,&p1,&p2);
	for(int i=1;i<=n;i++) scanf("%d",&ra[i]);
	if(p1) seg[0].init(p1);
	if(p2){
		int phi=p2,t=p2;
		for(int i=2;i*i<=t;i++) if(!(t%i)){
			phi=phi/i*(i-1);
			while(!(t%i)) t/=i;
		}
		if(t>1) phi=phi/t*(t-1);
		seg[1].init(phi);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&qt,&q1,&q2);
		if(qt==1) printf("%lld",seg[0].qmult(1,1,n));
		else {
			printf("%lld",qpow(k,seg[1].qmult(1,1,n),p2));
		}
		printf("\n");
	}
}