Chef likes toys. His favourite toy is an array of length N. This array contains only integers. He plays with this array every day. His favourite game with this array is Segment Multiplication. In this game, the second player tells the left and right side of a segment and some modulo. The first player should find the multiplication of all the integers in this segment of the array modulo the given modulus. Chef is playing this game. Of course, he is the first player and wants to win all the games. To win any game he should write the correct answer for each segment. Although Chef is very clever, he has no time to play games. Hence he asks you to help him. Write the program that solves this problem.

-----Input-----
The first line of the input contains an integer N denoting the number of elements in the given array. Next line contains N integers Ai separated with spaces. The third line contains the number of games T. Each of the next T lines contain 3 integers Li, Ri and Mi, the left side of the segment, the right side of segment and the modulo.

-----Output-----
For each game, output a single line containing the answer for the respective segment.

-----Constrdaints-----
- 1 ≤ N ≤ 100,000
- 1 ≤ Ai ≤ 100
- 1 ≤ T ≤ 100,000
- 1 ≤ Li ≤ Ri ≤ N
- 1 ≤ Mi ≤ 109

-----Example-----
Input:
5
1 2 3 4 5
4
1 2 3
2 3 4
1 1 1
1 5 1000000000

Output:
2
2
0
120

Difficulty: interview

Starter code:

Solutions:
# # # # n = int(input())
# # # # arr = list(map(int , input().split()))
# # # # for _ in range(int(input())):
# # # # 	l,r,mod = map(int , input().split())
# # # # 	pro = 1
# # # # 	for i in range(l - 1,r):
# # # # 		pro *= arr[i]
# # # # 	print(pro % mod) #sample testcases passed #TLE
# # # import numpy #or use math
# # # n = int(input())
# # # arr = list(map(int , input().split()))
# # # for _ in range(int(input())):
# # # 	l,r,mod = map(int , input().split())
# # # 	print(numpy.prod(arr[l - 1:r]) % mod) #sample cases passed, WA
# # import math
# # primes,dic,t = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97],{},0
# # for i in primes:
# #     dic[i] = t
# #     t += 1
# # def primeFactors(n,arr): 
# #     for i in range(2,int(math.sqrt(n)) + 1,2): 
# #         while(n % i == 0): 
# #             arr[dic[i]] += 1 
# #             n /= i
# #     if(n > 2):
# #         arr[dic[n]] += 1
# #     return arr
# # n = int(input())
# # A = list(map(int , input().split()))
# # dp = [0]*len(primes)
# # for i in range(1,n + 1):
# #     r = [dp[i - 1]].copy()
# #     dp.append(primeFactors(A[i - 1],r))
# # for _ in range(int(input())):
# #     li,ri,m=list(map(int,input().split()))
# #     ans = 1
# #     for i in range(len(primes)):
# #         ans *= (pow(primes[i],dp[ri][i] - dp[li - 1][i],m)) % m
# #     print(ans % m) #NZEC
# import math
# primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
# dic={}
# t=0
# for i in primes:
#     dic[i]=t
#     t+=1
# def primeFactors(n,arr): 
#     while(n % 2 == 0):
#         arr[dic[2]] += 1 
#         n /= 2
#     for i in range(3,int(math.sqrt(n))+1,2): 
#         while(n % i == 0): 
#             arr[dic[i]] += 1 
#             n /= i
#     if(n > 2): 
#         arr[dic[n]] += 1
#     return arr
# N = int(input())
# A = list(map(int , input().split()))
# dp = [[0]*len(primes)]
# for i in range(1,N + 1):
#     r = dp[i - 1].copy()
#     dp.append(primeFactors(A[i - 1],r))
# for _ in range(int(input())):
#     l,r,m = list(map(int , input().split()))
#     ans = 1
#     for i in range(len(primes)):
#         ans *= (pow(primes[i],dp[r][i] - dp[l - 1][i],m)) % m
#     print(ans % m)
import sys 
import math
input = sys.stdin.readline
primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
dic={}
t=0
for i in primes:
    dic[i]=t
    t+=1
def primeFactors(n,arr): 
    while n % 2 == 0: 
        arr[dic[2]]+=1 
        n = n / 2

    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0: 
            arr[dic[i]]+=1 
            n = n / i 

    if n > 2: 
        arr[dic[n]]+=1
    return arr
def main():
    N=int(input())
    A=list(map(int,input().split()))
    tp=[0]*len(primes)
    dp=[]
    dp.append(tp)
    for i in range(1,N+1):
        # print(i)
        r=dp[i-1].copy()
        t=primeFactors(A[i-1],r)
        dp.append(t)
    t=int(input())
    for _ in range(t):
        l,r,m=list(map(int,input().split()))
        if(m==1):
            print(0)
        else:
            ans=1
            for i in range(len(primes)):
                ans=ans*(pow(primes[i],dp[r][i]-dp[l-1][i],m))%m
            print(ans%m)
    
def __starting_point():
    main()
__starting_point()

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def getPrimeFactors(num):
    arr = [0]*25
    for index,i  in enumerate(primes):
        if i > num:
            break
        while num%i == 0:
            arr[index]+=1
            num //= i
    return arr

def findPower(arr, mod):
    ans = 1
    for index,i in enumerate(arr):
        if i != 0:
            ans*=pow(primes[index], i, mod)
            if ans > mod:
                ans%=mod
    return ans%mod

n = int(input())
arr = list(map(int, input().strip().split()))

cumarr = []
temp = [0]*25
cumarr.append(temp.copy())

for i in arr:
    for index,p  in enumerate(primes):
        if p > i:
            break
        while i%p == 0:
            temp[index]+=1
            i //= p
    cumarr.append(temp.copy())


for x in range(int(input())):
    l, r, m = map(int, input().strip().split())
    ans = findPower([x-y for x,y in zip(cumarr[r], cumarr[l-1])], m)
    print(ans)

from sys import stdin

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

def getPrime(n):
    
    arr = [0]*25
    for i,p in enumerate( primes ):
        if p > n:
            break
        
        while n % p == 0:
            arr[i] += 1
            n //= p
            
    
    return arr


def matAdd(matA , matB):
    
    arr = []
    for i in range(25):
        arr.append( matB[i] + matA[i] )
        
    return arr


def matSub( matA , matB ):
    
    arr = []
    
    for i in range(25):
        arr.append( matA[i] - matB[i] )
        
    return arr


def getPow( arr , M ):
    
    ans = 1
    
    for i , a in enumerate( arr ):
        
        if a != 0:

            ans *= pow( primes[i] , a , M )
        
            if ans > M:
                ans %= M
            
    return ans%M



n = int(input())
arr = list(map(int,input().strip().split()))

temp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
pref = [ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ]


for a in arr:
    
    for i,p in enumerate( primes ):
        if p > a:
            break
        
        while a % p == 0:
            temp[i] += 1
            a //= p
    
    pref.append( temp.copy() )

    
for po in range( int(input()) ):
    
    a , b , M = map( int , input().strip().split() )
    
    ans = getPow( [ x-y for (x,y) in zip( pref[b] , pref[a-1] ) ] , M )
        
    print(ans%M)