记录编号	326442	评测结果	AWAWTETAEE
题目名称	学姐的巧克力盒	最终得分	30
用户昵称	Cydiater	是否通过	未通过
代码语言	C++	运行时间	7.982 s
提交时间	2016-10-21 07:58:22	内存使用	26.26 MiB

//C
//by Cydiater
//2016.10.20
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
#define ll long long
#define up(i,j,n)		for(int i=j;i<=n;i++)
#define down(i,j,n)		for(int i=j;i>=n;i--)
#define FILE "chocolatebox"
const ll MAXN=1e6+5;
const ll oo=1LL<<60;
const ll mod1=1e9+7;
const ll mod2=996919243;
inline ll read(){
	char ch=getchar();ll x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
ll N,M,K,P1,P2,a[MAXN],flag,L,R,pre[MAXN],t[MAXN];
void init(){
	N=read();M=read();K=read();P1=read();P2=read();
	up(i,1,N)a[i]=read();
}
namespace solution1{
	void build(int leftt,int rightt,int root){
		if(leftt==rightt){
			t[root]=a[leftt]%P1;
			return;
		}
		int mid=(leftt+rightt)>>1;
		build(leftt,mid,root<<1);
		build(mid+1,rightt,root<<1|1);
		t[root]=(t[root<<1]*t[root<<1|1])%P1;
	}
	ll get(int leftt,int rightt,int root){
		if(leftt>R||rightt<L)	return 1;
		if(leftt>=L&&rightt<=R)	return t[root];
		int mid=(leftt+rightt)>>1;
		return (get(leftt,mid,root<<1)*get(mid+1,rightt,root<<1|1))%P1;
	}
	void slove(){
		while(M--){
			flag=read();L=read();R=read();
			printf("%lld\n",get(1,N,1));
		}
	}
}
namespace solution2{
	void exgcd(ll a,ll b,ll &x,ll &y){
		if(b==0){x=1;y=0;return;}
		exgcd(b,a%b,x,y);
		ll t=x;x=y;y=t-a/b*y;
	}
	ll inv(ll a,ll b){
		ll x,y;
		exgcd(a,b,x,y);
		while(x<0)x+=b;
		return x;
	}
	void build(){
		pre[0]=1;
		up(i,1,N)pre[i]=(pre[i-1]*a[i])%P1;
	}
	void slove(){
		while(M--){
			flag=read();L=read();R=read();
			printf("%lld\n",((pre[R]*inv(pre[L-1],P1)+P1)%P1+P1)%P1);
		}
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	init();
	if(P1!=mod1&&P1!=mod2){
		using namespace solution1;
		build(1,N,1);
		slove();
	}else{
		using namespace solution2;
		build();
		slove();
	}
	return 0;
}