解析
大降智题。
受相逢是问候的影响，第一眼直接线段树，写完WA完才发现这个玩意没有结合律。
然后开始用
x
y
z
=
(
x
y
)
y
z
?
1
x^{y^z}=(x^y)^{y^{z-1}}
xyz=(xy)yz?1 这样的东西嗯做，结果只是在玩泥巴。
lemma：迭代求 φ \varphi φ 的次数是 log 级别的。
证明：偶数的 φ \varphi φ 至少折半，对于 n > 2 n>2 n>2， φ ( n ) \varphi(n) φ(n) 恒为偶数，因为 gcd ? ( i , n ) = g c d ( n ? i , n ) \gcd(i,n)=gcd(n-i,n) gcd(i,n)=gcd(n?i,n)。
所以直接暴力往后扫模数为1就返回就可以了。
//luogu
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
using namespace std;
const int N=1e5+100;
//const int mod=998244353;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
#define pr pair<ll,bool>
#define mkp make_pair
inline pr ksm(ll x,ll k,int mod){
ll res(1);bool flag=0;
while(k){
if(k&1){
res=res*x;
if(res>=mod){
res%=mod;flag=1;
}
}
x=x*x;
if(x>=mod&&k>1){
x%=mod;
flag=1;
}
k>>=1;
}
return mkp(res,flag);
}
map<int,int>mp;
int n,m;
int w[N];
inline int getphi(int x){
if(mp.count(x)) return mp[x];
int ori=x;
int w=sqrt(x),res=x;
for(int i=2;i<=w;i++){
if(x%i==0){
res=1ll*res*(i-1)/i;
while(x%i==0) x/=i;
}
}
if(x>1) res=1ll*res*(x-1)/x;
return mp[ori]=res;
}
pr calc(int l,int r,int mod){
if(l==r){return mkp(w[l]%mod,w[l]>=mod);}
if(mod==1) return mkp(0,1);
int phi=getphi(mod);
pr o=calc(l+1,r,phi);
return ksm(w[l],o.first+o.second*phi,mod);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();int mod=read();
for(int i=1;i<=n;i++) w[i]=read();
m=read();
for(int i=1;i<=m;i++){
int l=read(),r=read();
printf("%lld\n",calc(l,r,mod).first);
}
return 0;
}
/*
*/
