#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 1000010;
int phi(int x){
	int ret = x;
	for(int i=2;i*i<=x; ++i){
		if(x % i == 0){
			ret /= i;ret *= (i-1);
			while(x % i == 0) x /= i;
		}
	}
	if(x^1) ret /= x,ret *= (x-1);
	return ret;
}
int p1,p2,T[maxn<<2],h[maxn<<2],M;
int n,m,k,P;
inline void update(int x){
	T[x] = T[x<<1]*T[x<<1|1]%p1;
	h[x] = h[x<<1]*h[x<<1|1]%p2;
}
void build(int n){
	for(M=1;M<(n+1);M<<=1);
	for(int i=M+1;i<=M+n;++i) read(T[i]),h[i]=T[i],h[i]%=p2,T[i]%=p1;
	for(int i=M-1;i;--i) update(i);
}
int query1(int s,int t){
	int ret = 1;
	for(s += M-1,t += M+1;s^t^1;s>>=1,t>>=1){
		if(~s&1) ret = ret*T[s^1]%p1;
		if( t&1) ret = ret*T[t^1]%p1;
	}return ret;
}
int query2(int s,int t){
	int ret = 1;
	for(s += M-1,t += M+1;s^t^1;s>>=1,t>>=1){
		if(~s&1) ret = ret*h[s^1]%p2;
		if( t&1) ret = ret*h[t^1]%p2;
	}return ret;
}
inline int qpow(int x,int p){
	int ret = 1;
	for(;p;p>>=1,x=x*x%P) if(p&1) ret = ret*x%P;
	return ret;
}
int main(){
	freopen("chocolatebox.in","r",stdin);
	freopen("chocolatebox.out","w",stdout);
	read(n);read(m);read(k);read(p1);read(P);
	p2 = phi(P);
	build(n);
	int cmd,u,v;
	while(m--){
		read(cmd);read(u);read(v);
		if(cmd == 1) printf("%d\n",query1(u,v));
		else printf("%d\n",qpow(k,query2(u,v)) );
	}
	//getchar();getchar();
	fclose(stdin);fclose(stdout);
	return 0;
}