#include<cstdio>

#include<iostream>

using namespace std;

int pi[],phi[],lim;

int a[];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

int get_phi(int n)

{

    int ph=n;

    for(int i=;i*i<=n;++i)

        if(!(n%i))

        {

            ph=ph/i*(i-);

            while(!(n%i)) n/=i;

        }

    if(n>) ph=ph/n*(n-);

    return ph;

}

int Pow(int a,int b,int mod,bool &flag)

{

    int res=;

    while(b)

    {

        if(b&)

        {

            flag|=(1LL*res*a>=mod);

            res=1LL*res*a%mod;

        }

        flag|=(1LL*a*a>=mod);

        a=1LL*a*a%mod;

        b>>=;

    }

    return res;

}

int f(int x,int dep)

{

    if(dep>lim)

    {

        x-=dep-lim;

        dep=lim;

    }

    if(dep==) return a[x]%pi[];

    int tmp=a[x];

    if(tmp>=phi[dep-]) tmp=tmp%phi[dep-]+phi[dep-];

    x--;

    bool flag;

    for(int i=dep-;i;--i)

    {

        flag=false;

        tmp=Pow(a[x],tmp,pi[i],flag);

        if(flag) tmp+=phi[i-];

        x--;

    }

    return tmp;

}

int main()

{

//    freopen("data.in","r",stdin);

//    freopen("my.out","w",stdout);

    int n,mod;

    read(n); read(mod);

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

    int tmp=mod;

    while(pi[lim]!=)

    {

        pi[++lim]=tmp;

        phi[lim]=get_phi(tmp);

        tmp=phi[lim];

    }

    int q;

    read(q);

    int l,r;

    while(q--)

    {

        read(l); read(r);

        printf("%d\n",f(r,r-l+));

    }

    return ;

}