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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from sys import stdin\n\nprimes = [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]\n\ndef getPrime(n):\n    \n    arr = [0]*25\n    for i,p in enumerate( primes ):\n        if p > n:\n            break\n        \n        while n % p == 0:\n            arr[i] += 1\n            n //= p\n            \n    \n    return arr\n\n\ndef matAdd(matA , matB):\n    \n    arr = []\n    for i in range(25):\n        arr.append( matB[i] + matA[i] )\n        \n    return arr\n\n\ndef matSub( matA , matB ):\n    \n    arr = []\n    \n    for i in range(25):\n        arr.append( matA[i] - matB[i] )\n        \n    return arr\n\n\ndef getPow( arr , M ):\n    \n    ans = 1\n    \n    for i , a in enumerate( arr ):\n        \n        if a != 0:\n\n            ans *= pow( primes[i] , a , M )\n        \n            if ans > M:\n                ans %= M\n            \n    return ans%M\n\n\n\nn = int(input())\narr = list(map(int,input().strip().split()))\n\ntemp = [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]\npref = [ [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] ]\n\n\nfor a in arr:\n    \n    for i,p in enumerate( primes ):\n        if p > a:\n            break\n        \n        while a % p == 0:\n            temp[i] += 1\n            a //= p\n    \n    pref.append( temp.copy() )\n\n    \nfor po in range( int(input()) ):\n    \n    a , b , M = map( int , input().strip().split() )\n    \n    ans = getPow( [ x-y for (x,y) in zip( pref[b] , pref[a-1] ) ] , M )\n        \n    print(ans%M)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14377