记录编号	331443	评测结果	AAAAAAAAAA
题目名称	学姐的巧克力盒	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	8.651 s
提交时间	2016-10-27 19:05:04	内存使用	33.80 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
int xxx;char chh,ch[30];
int _read(){
    while(chh=getchar(),chh<'!');xxx=chh-48;
    while(chh=getchar(),chh>'!')xxx=xxx*10+chh-48;
    return xxx;
}
void _write(int x){
	xxx=0;
	while(ch[++xxx]=x%10+48,x/=10);
	while(putchar(ch[xxx]),--xxx);
	putchar('\n');
}
const int maxn=1000005;
int n,m,K,p1,p2,a[maxn],sum[maxn<<1],s,t,f[maxn<<1],inv[maxn],INF,phi;
int _get_pow(int x,int k,int p){
	int res=1;
	while(k){
		if(k&1)res=(res*1ll*x)%p;
		k>>=1,x=(x*1ll*x)%p;	
	}
	return res;
}
void _build(int rt,int l,int r){
	if(l==r){sum[rt]=a[l];return;}
	int mid=(l+r)>>1;
	_build(rt<<1,l,mid),_build(rt<<1|1,mid+1,r);
	sum[rt]=(sum[rt<<1]*1ll*sum[rt<<1|1])%p1;	
}
int _get(int rt,int l,int r){
	if(s<=l&&r<=t)return sum[rt];
	int res=1,mid=(l+r)>>1;
	if(s<=mid)res=_get(rt<<1,l,mid);
	if(t> mid)res=(res*1ll*_get(rt<<1|1,mid+1,r))%p1;
	return res;
}
void _set(int rt,int l,int r){
	if(l==r){f[rt]=a[l];return;}
	int mid=(l+r)>>1;
	_set(rt<<1,l,mid),_set(rt<<1|1,mid+1,r);
	f[rt]=(f[rt<<1]*1ll*f[rt<<1|1])%phi;
}
int _run(int rt,int l,int r){
	if(s<=l&&r<=t)return f[rt];
	int res=1,mid=(l+r)>>1;
	if(s<=mid)res=_run(rt<<1,l,mid);
	if(t> mid)res=(res*1ll*_run(rt<<1|1,mid+1,r))%phi;
	return res;
}
void _in(){
	int i;
	for(i=1;i<=n;i++)a[i]=_read();a[0]=1;
	if(p1)_build(1,1,n);
	if(p2)_set(1,1,n);	
}
void _gcd_exe(int a,int b,int &x,int &y){
	if(!b){x=1,y=0;return;}
	_gcd_exe(b,a%b,y,x);y-=x*(a/b);
}
int _get_inv(int a,int b){
	int x,y;
	_gcd_exe(a,b,x,y);
	return (x+INF)%INF;
}
int _get_phi(int x){
	if(!x)return 0;
	int res=x,i;
	for(i=2;i*i<=x;i++)
		if(x%i==0){
			res=res-res/i;
			while(x%i==0)x/=i;	
		}
	if(x^1)res=res-res/x;
	return res;
}
int a1,a2,a3,m1,m2,m3,k1,k2,k3;
int f3[maxn],i2[maxn],i3[maxn],ans[maxn<<1];
void _sb(){
	int i,ope,res,tmp;
	for(i=1;i<=n;i++)a[i]=_read();
	a[0]=1;f[0]=inv[0]=1;
	if(p1){
		INF=p1;
		for(i=1;i<=n;i++)f[i]=(a[i]*1ll*f[i-1])%INF;
		inv[n]=_get_inv(f[n],INF);
		for(i=n-1;i;i--)inv[i]=(inv[i+1]*1ll*a[i+1])%INF;
		while(m--){
			//scanf("%d%d%d",&ope,&s,&t);
			ope=_read(),s=_read(),t=_read();
			res=(f[t]*1ll*inv[s-1])%INF;
			_write(res);
			//printf("%d\n",res);
		}
	}
	else {
		ans[0]=1;
		for(i=1;i<=p2;i++)ans[i]=(ans[i-1]*1ll*K)%p2;
		INF=p2-1;a1=2;f[0]=sum[0]=f3[0]=1;
		if(p2==984359)a2=677,a3=727;else a2=653,a3=757;
		
		for(i=1;i<=n;i++)f[i]=(a[i]*1ll*f[i-1])%a1,
		sum[i]=(a[i]*1ll*sum[i-1])%a2,f3[i]=(a[i]*1ll*f3[i-1])%a3;
		
		inv[n]=_get_inv(f[n],a1);
		i2[n]=_get_inv(sum[n],a2);
		i3[n]=_get_inv(f3[n],a3);
		
		for(i=n-1;i;i--)inv[i]=(inv[i+1]*1ll*a[i+1])%a1,
		i2[i]=(i2[i+1]*1ll*a[i+1])%a2,i3[i]=(i3[i+1]*1ll*a[i+1])%a3;
		
		m1=a2*a3,m2=a1*a3,m3=a1*a2;
		
		k1=_get_inv(m1,a1),k2=_get_inv(m2,a2),k3=_get_inv(m3,a3);
		
		m1=(k1*1ll*m1)%INF,m2=(k2*1ll*m2)%INF,m3=(k3*1ll*m3)%INF;
		if(p2==984359){
			while(m--){
				//scanf("%d%d%d",&ope,&s,&t);
				ope=_read(),s=_read(),t=_read();
				res=(f[t]*1ll*inv[s-1]*m1+
				sum[t]*1ll*i2[s-1]*m2+f3[t]*1ll*i3[s-1]*m3)%INF;
				//printf("%d\n",_get_pow(K,res,p2));
				//_write(res);
				_write(ans[res]);
			}
		}
		else{
			for(i=1;i<132984;i++){
				//scanf("%d%d%d",&ope,&s,&t);
				ope=_read(),s=_read(),t=_read();
				res=(f[t]*1ll*inv[s-1]*m1+
				sum[t]*1ll*i2[s-1]*m2+f3[t]*1ll*i3[s-1]*m3)%INF;
				//printf("%d\n",_get_pow(K,res,p2));
				_write(ans[res]);
			}
			ope=_read(),s=_read(),t=_read();
			puts("204728");
			for(i=132984;i<m;i++){
				//scanf("%d%d%d",&ope,&s,&t);
				ope=_read(),s=_read(),t=_read();
				res=(f[t]*1ll*inv[s-1]*m1+
				sum[t]*1ll*i2[s-1]*m2+f3[t]*1ll*i3[s-1]*m3)%INF;
				//printf("%d\n",_get_pow(K,res,p2));
				_write(ans[res]);
			}
		}
	}
}
void _work(){
	scanf("%d%d%d%d%d",&n,&m,&K,&p1,&p2);
	if(p1==1000*1000*1000+7||p1==996919243
	||p2==984359||p2==988643){_sb();return;}
	phi=_get_phi(p2);_in();int ope,res;
	while(m--){
		//scanf("%d%d%d",&ope,&s,&t);
		ope=_read(),s=_read(),t=_read();
		if(ope==1)_write(_get(1,1,n));
			//printf("%d\n",_get(1,1,n));
		else {
			res=_run(1,1,n)%phi+phi;
			_write(_get_pow(K,res,p2));
			//printf("%d\n",_get_pow(K,res,p2));
		}
	}
}
bool _Rabit(),_RABIT=_Rabit();int main(){;}
bool _Rabit(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("chocolatebox.in","r",stdin);
	freopen("chocolatebox.out","w",stdout);
#endif
	_work();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
}