记录编号	327106	评测结果	AAAAAAAAAA
题目名称	学姐的巧克力盒	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	17.777 s
提交时间	2016-10-21 19:51:06	内存使用	134.81 MiB

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cmath>
#define lc(o) o<<1
#define rc(o) o<<1|1

const int MAXLEN=52*1024*1024;
char str[MAXLEN+1],*pos=str;
FILE *in=fopen("chocolatebox.in","r"),*out=fopen("chocolatebox.out","w");

inline int read(){
	int _x=0;
	for(;(*pos)>57||(*pos)<48;pos++);
	for(;(*pos)>=48&&(*pos)<=57;_x=(_x<<3)+(_x<<1)+(*pos)-48,pos++);
	return _x;
}

char fout[MAXLEN],tem[30];int len,tlen;
inline void print(int x){
	tlen=0;
	for(x==0?tem[tlen++]='0':0 ; x ; tem[tlen++]=x%10+'0',x/=10);
	while(tlen--) fout[len++]=tem[tlen];
	fout[len++]='\n';
}

int ans,n,m,phi,k,p1,p2,kp[40],mul[4000010][2];

void build(int o,int l,int r){
	if(l==r){
		mul[o][0]=read();
		if(p1) mul[o][0]%=p1;
		if(p2) mul[o][1]=mul[o][0]%phi;
		return;
	}
	int mid=(l+r)>>1,ll=lc(o),rr=rc(o);
	build(ll,l,mid);
	build(rr,mid+1,r);
	if(p1) mul[o][0]=(1ll*mul[ll][0]*mul[rr][0])%p1;
	if(p2) mul[o][1]=(1ll*mul[ll][1]*mul[rr][1])%phi;
}

int query(int o,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return mul[o][0];
	int mid=(l+r)>>1; int re=1;
	if(ql<=mid) re=(1ll*re*query(lc(o),l,mid,ql,qr))%p1;
	if(mid<qr) re=(1ll*re*query(rc(o),mid+1,r,ql,qr))%p1;
	return re;
}

int query2(int o,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return mul[o][1]%phi;
	int mid=(l+r)>>1; int re=1;
	if(ql<=mid) re=(1ll*re*query2(lc(o),l,mid,ql,qr))%phi;
	if(mid<qr) re=(1ll*re*query2(rc(o),mid+1,r,ql,qr))%phi;
	return re;
}

int pow2(int b){
	int now=1,re=1;
	while(b){
		if(b&1) re=(1ll*re*kp[now])%p2;
		now++; b>>=1;
	}
	return re;
}

inline void getphi(){
	int x=p2,y=sqrt(x);phi=p2;
	for(int i=2;i<=y;i++)
		if(!(x%i)){
			phi=phi-phi/i;
			while(!(x%i)) x/=i;
		}
	if(x>1) phi=phi/x*(x-1);
}

int main()
{
	fread(str,1,MAXLEN,in);
	n=read(); m=read(); k=read(); p1=read(); p2=read();
	if(p2) {kp[1]=k;for(int i=2;i<=32;i++) kp[i]=1ll*kp[i-1]*kp[i-1]%p2;}
	if(p2) getphi();
	build(1,1,n);
	while(m--){
		int p=read(),l=read(),r=read();
		if(p&1) print(query(1,1,n,l,r));
		else print(pow2(query2(1,1,n,l,r)));
	}
	fwrite(fout,1,len-1,out);
	return 0;
}