#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#define maxn 100010

#define Mod(a,b) a<b?a:a%b+b

using namespace std;

long long n,m,a[maxn];

map<long long,long long>p;

long long qread(){

    long long i=,j=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}

    while(ch<=''&&ch>='')i=i*+ch-'',ch=getchar();

    return i*j;

}

long long Pow(long long x,long long y,long long mod){

    long long res=;

    while(y){

        if(y&)res=Mod(res*x,mod);

        x=Mod(x*x,mod);

        y>>=;

    }

    return res;

}

long long phi(long long k){

    long long s=k,x=k;

    if(p[k])return p[k];

    for(long long i=;i*i<=k;i++){

        if(k%i==)s=s/i*(i-);

        while(k%i==)k/=i;

    }

    if(k>)s=s/k*(k-);

    p[x]=s;return s;

}

long long solve(int l,int r,long long mod){

    if(l==r||mod==)return Mod(a[l],mod);

    return Pow(a[l],solve(l+,r,phi(mod)),mod);

}

int main(){

    freopen("Cola.txt","r",stdin);

    n=qread();m=qread();

    for(int i=;i<=n;i++)a[i]=qread();

    int Q;scanf("%d",&Q);

    int l,r;

    while(Q--){

        scanf("%d%d",&l,&r);

        cout<<solve(l,r,m)%m<<endl;

    }

    return ;

}