#include<stdio.h>
long long inline scan()
{
long long x=0;
int c = getchar();
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = getchar());
if(c=='-') {neg=1;c=getchar();}
for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
return x;
}
long long exp(long long a,long long b,long long mod)
{
long long result=1;
while(b)
{
if(b%2==1)
{
result*= a;
while(result>=mod)
result-=mod;
}
b=b>>1;
a*= a;
while(a>=mod)
a-=mod;
}
return result;
}
/*
long long exp(int a, int b,long long mod){
long long r;
if(b==0) return 1;
r = exp(a,b/2,mod);
r = (r*r)%mod;
if(b%2) r = (r*a)%mod;
return r;
}
*/
int np[100001][26]={0};
int tmp[101][26]={0};
int prime[26]={0};
//int invprime[101];
int main()
{
int i,j,n,t,k,l,r;
long long temp,m,ans;
prime[1]=2;
prime[2]=3;
prime[3]=5;
prime[4]=7;
prime[5]=11;
prime[6]=13;
prime[7]=17;
prime[8]=19;
prime[9]=23;
prime[10]=29;
prime[11]=31;
prime[12]=37;
prime[13]=41;
prime[14]=43;
prime[15]=47;
prime[16]=53;
prime[17]=59;
prime[18]=61;
prime[19]=67;
prime[20]=71;
prime[21]=73;
prime[22]=79;
prime[23]=83;
prime[24]=89;
prime[25]=97;
for(i=2;i<101;i++)
{
k=i;
temp=1;
for(j=prime[temp];j*j<=k;)
{
while(k%j==0)
{
tmp[i][temp]++;
k/=j;
}
temp++;
j=prime[temp];
}
if(k>1)
{
for(j=1;j<26;j++)
if(prime[j]==k)
break;
tmp[i][j]++;
}
}
n=scan();
/*for(i=1;i<=n;i++)
{
temp=scan();
for(j=1;j<101;j++)
{
np[i][j]=tmp[temp][j];
}
}
for(i=2;i<=n;i++)
for(j=1;j<101;j++)
np[i][j]+=np[i-1][j];
*/
temp=scan();
for(i=1;i<26;i++)
np[1][i]=tmp[temp][i];
for(i=2;i<=n;i++)
{
temp=scan();
for(j=1;j<26;j++)
np[i][j]=np[i-1][j]+tmp[temp][j];
}
t=scan();
while(t--)
{
l=scan();
r=scan();
m=scan();
if(m==1) printf("0\n");
else
{
ans=1;
for(i=1;i<26;i++)
{
temp=np[r][i]-np[l-1][i];
if(temp)
ans=(ans*exp(prime[i],temp,m))%m;
if(ans==0) break;
}
printf("%lld\n",ans);
}
}
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KbG9uZyBsb25nIGlubGluZSBzY2FuKCkKewogICAgbG9uZyBsb25nIHg9MDsKICAgIGludCBjID0gZ2V0Y2hhcigpOwogICAgaW50IG5lZyA9IDA7CiAgICBmb3IoOygoYzw0OCB8fCBjPjU3KSAmJiBjICE9ICctJyk7YyA9IGdldGNoYXIoKSk7CiAgICBpZihjPT0nLScpIHtuZWc9MTtjPWdldGNoYXIoKTt9CiAgICBmb3IoO2M+NDcgJiYgYzw1ODtjID0gZ2V0Y2hhcigpKSB7eCA9ICh4PDwxKSArICh4PDwzKSArIGMgLSA0ODt9CiAgICBpZihuZWcpIHg9LXg7CiAgICByZXR1cm4geDsKfQoKbG9uZyBsb25nIGV4cChsb25nIGxvbmcgYSxsb25nIGxvbmcgYixsb25nIGxvbmcgbW9kKQp7CgogICAgbG9uZyBsb25nIHJlc3VsdD0xOwogICAgd2hpbGUoYikKICAgIHsKICAgICAgICBpZihiJTI9PTEpCiAgICAgICAgewogICAgICAgICAgICByZXN1bHQqPSBhOwogICAgICAgICAgICB3aGlsZShyZXN1bHQ+PW1vZCkKICAgICAgICAgICAgICAgIHJlc3VsdC09bW9kOwogICAgICAgIH0KICAgICAgICBiPWI+PjE7CiAgICAgICAgYSo9IGE7CiAgICAgICAgd2hpbGUoYT49bW9kKQogICAgICAgICAgICBhLT1tb2Q7CiAgICB9CiAgICByZXR1cm4gcmVzdWx0Owp9Ci8qCmxvbmcgbG9uZyBleHAoaW50IGEsIGludCBiLGxvbmcgbG9uZyBtb2Qpewpsb25nIGxvbmcgcjsKaWYoYj09MCkgcmV0dXJuIDE7CnIgPSBleHAoYSxiLzIsbW9kKTsKciA9IChyKnIpJW1vZDsKaWYoYiUyKSByID0gKHIqYSklbW9kOwpyZXR1cm4gcjsKfQoqLwppbnQgbnBbMTAwMDAxXVsyNl09ezB9OwppbnQgdG1wWzEwMV1bMjZdPXswfTsKaW50IHByaW1lWzI2XT17MH07Ci8vaW50IGludnByaW1lWzEwMV07CmludCBtYWluKCkKewogICAgaW50IGksaixuLHQsayxsLHI7CiAgICBsb25nIGxvbmcgdGVtcCxtLGFuczsKICAgIHByaW1lWzFdPTI7CiAgICBwcmltZVsyXT0zOwogICAgcHJpbWVbM109NTsKICAgIHByaW1lWzRdPTc7CiAgICBwcmltZVs1XT0xMTsKICAgIHByaW1lWzZdPTEzOwogICAgcHJpbWVbN109MTc7CiAgICBwcmltZVs4XT0xOTsKICAgIHByaW1lWzldPTIzOwogICAgcHJpbWVbMTBdPTI5OwogICAgcHJpbWVbMTFdPTMxOwogICAgcHJpbWVbMTJdPTM3OwogICAgcHJpbWVbMTNdPTQxOwogICAgcHJpbWVbMTRdPTQzOwogICAgcHJpbWVbMTVdPTQ3OwogICAgcHJpbWVbMTZdPTUzOwogICAgcHJpbWVbMTddPTU5OwogICAgcHJpbWVbMThdPTYxOwogICAgcHJpbWVbMTldPTY3OwogICAgcHJpbWVbMjBdPTcxOwogICAgcHJpbWVbMjFdPTczOwogICAgcHJpbWVbMjJdPTc5OwogICAgcHJpbWVbMjNdPTgzOwogICAgcHJpbWVbMjRdPTg5OwogICAgcHJpbWVbMjVdPTk3OwogICAgZm9yKGk9MjtpPDEwMTtpKyspCiAgICB7CiAgICAgICAgaz1pOwogICAgICAgIHRlbXA9MTsKICAgICAgICBmb3Ioaj1wcmltZVt0ZW1wXTtqKmo8PWs7KQogICAgICAgIHsKICAgICAgICAgICAgd2hpbGUoayVqPT0wKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB0bXBbaV1bdGVtcF0rKzsKICAgICAgICAgICAgICAgIGsvPWo7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgdGVtcCsrOwogICAgICAgICAgICBqPXByaW1lW3RlbXBdOwogICAgICAgIH0KICAgICAgICBpZihrPjEpCiAgICAgICAgewogICAgICAgICAgICBmb3Ioaj0xO2o8MjY7aisrKQogICAgICAgICAgICAgICAgaWYocHJpbWVbal09PWspCiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIHRtcFtpXVtqXSsrOwogICAgICAgIH0KICAgIH0KICAgIG49c2NhbigpOwoKICAgIC8qZm9yKGk9MTtpPD1uO2krKykKICAgIHsKICAgICAgICB0ZW1wPXNjYW4oKTsKICAgICAgICBmb3Ioaj0xO2o8MTAxO2orKykKICAgICAgICB7CiAgICAgICAgICAgIG5wW2ldW2pdPXRtcFt0ZW1wXVtqXTsKICAgICAgICB9CiAgICB9CgogICAgZm9yKGk9MjtpPD1uO2krKykKICAgICAgICBmb3Ioaj0xO2o8MTAxO2orKykKICAgICAgICAgICAgbnBbaV1bal0rPW5wW2ktMV1bal07CiAgICAqLwogICAgdGVtcD1zY2FuKCk7CiAgICBmb3IoaT0xO2k8MjY7aSsrKQogICAgICAgIG5wWzFdW2ldPXRtcFt0ZW1wXVtpXTsKCiAgICBmb3IoaT0yO2k8PW47aSsrKQogICAgewogICAgICAgIHRlbXA9c2NhbigpOwogICAgICAgIGZvcihqPTE7ajwyNjtqKyspCiAgICAgICAgICAgIG5wW2ldW2pdPW5wW2ktMV1bal0rdG1wW3RlbXBdW2pdOwogICAgfQoKICAgIHQ9c2NhbigpOwogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIGw9c2NhbigpOwogICAgICAgIHI9c2NhbigpOwogICAgICAgIG09c2NhbigpOwogICAgICAgIGlmKG09PTEpIHByaW50ZigiMFxuIik7CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgYW5zPTE7CiAgICAgICAgICAgIGZvcihpPTE7aTwyNjtpKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHRlbXA9bnBbcl1baV0tbnBbbC0xXVtpXTsKICAgICAgICAgICAgICAgIGlmKHRlbXApCiAgICAgICAgICAgICAgICAgICAgYW5zPShhbnMqZXhwKHByaW1lW2ldLHRlbXAsbSkpJW07CiAgICAgICAgICAgICAgICBpZihhbnM9PTApIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHByaW50ZigiJWxsZFxuIixhbnMpOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9CgoK