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: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
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):
		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)
main()


import sys

def solve(n, arr, queries):
	store = {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: []}
	temp = [0 for i in range(n + 1)]
	for ele in store:
		store[ele] = temp[:]
	for (i, ele) in enumerate(arr):
		reqIndex = i + 1
		for num in store:
			count = 0
			while ele % num == 0 and ele != 0:
				count += 1
				ele = ele // num
			store[num][reqIndex] = store[num][reqIndex - 1] + count
	for ele in queries:
		(l, r, m) = (ele[0], ele[1], ele[2])
		if m == 1:
			sys.stdout.write(str(0) + '\n')
			continue
		ans = 1
		for ele in store:
			count = store[ele][r] - store[ele][l - 1]
			ans *= pow(ele, count, m)
			ans = ans % m
		ans = ans % m
		sys.stdout.write(str(ans) + '\n')
n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().strip().split()))
T = int(sys.stdin.readline().strip())
queries = []
while T:
	(l, r, m) = map(int, sys.stdin.readline().strip().split())
	queries.append([l, r, m])
	T -= 1
solve(n, arr, queries)


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)


import bisect
import sys
import math

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_list_strings():
	return list(map(str, sys.stdin.readline().strip().split()))

def solve():
	n = get_int()
	arr = get_list()
	t = get_int()
	store = {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: []}
	temp = [0 for i in range(n + 1)]
	for ele in store:
		store[ele] = temp[:]
	for (i, ele) in enumerate(arr):
		for num in store:
			count = 0
			while ele % num == 0 and ele != 0:
				count += 1
				ele = ele // num
			store[num][i + 1] = store[num][i] + count
	while t:
		(l, r, m) = get_ints()
		if m == 1:
			sys.stdout.write(str(0) + '\n')
			t -= 1
			continue
		ans = 1
		for ele in store:
			ans *= pow(ele, store[ele][r] - store[ele][l - 1], m)
			ans = ans % m
		sys.stdout.write(str(ans) + '\n')
		t -= 1
solve()


def main():
	N = int(input())
	A = list(map(int, input().strip().split(' ')))
	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]
	counting = [[0] * len(primes) for i in range(len(A))]

	def div(n):
		CC = [0] * len(primes)
		for i in range(len(primes)):
			while n % primes[i] == 0:
				CC[i] += 1
				n = n // primes[i]
			if n == 1:
				return CC
		return CC
	for i in range(len(A)):
		C = div(A[i])
		for j in range(len(primes)):
			if i > 0:
				counting[i][j] = counting[i - 1][j] + C[j]
			else:
				counting[i][j] = C[j]
	for _ in range(int(input())):
		(L, R, M) = list(map(int, input().strip().split(' ')))
		L -= 1
		R -= 1
		if L > 0:
			CC = [counting[R][j] - counting[L - 1][j] for j in range(len(primes))]
		else:
			CC = [counting[R][j] for j in range(len(primes))]
		temp = 1
		for j in range(len(CC)):
			temp *= pow(primes[j], CC[j], M)
			temp %= M
		print(temp)
main()


def main():
	N = int(input())
	a = [int(x) for x in input().split()]
	p = [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]
	c = [[0 for x in range(25)] for y in range(N)]

	def fct(n):
		fact = [0] * 25
		for i in range(25):
			while n % p[i] == 0:
				fact[i] += 1
				n = n // p[i]
			if n == 1:
				return fact
		return fact
	for i in range(N):
		hc = fct(a[i])
		for j in range(25):
			if i > 0:
				c[i][j] = c[i - 1][j] + hc[j]
			else:
				c[i][j] = hc[j]
	for _ in range(int(input())):
		(L, R, M) = map(int, input().split())
		L = L - 1
		R = R - 1
		if L > 0:
			t = [c[R][i] - c[L - 1][i] for i in range(25)]
		else:
			t = [c[R][i] for i in range(25)]
		ans = 1
		for i in range(25):
			ans *= pow(p[i], t[i], M)
			ans %= M
		print(ans)
main()


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)