You are given an array ${A}$ of size $N$. You are asked to answer ${Q}$ queries. 

Each query is of the form : 

${ij x}$ 

You need to print Yes if ${x}$ divides the value returned from $find(i,j)$ function, otherwise print No.

find(int i,int j)
{
    if(i>j) return 1;
    ans = pow(A[i],find(i+1,j))
    return ans
}

Input Format

First line of the input contains $N$. Next line contains $N$ space separated numbers. The line, thereafter, contains ${Q}$ , the number of queries to follow. Each of the next ${Q}$ lines contains three positive integer ${i}$, $j$ and ${x}$.

Output Format

For each query display Yes or No as explained above.

Constraints 

$2\leq N\leq2\times10^5$ 

$2\leq Q\leq3\times10^5$ 

$1\leq i,j\leq N$ 

$i\leq j$ 

$1\leq x\leq10^{16}$ 

${{0}\leq$ value of array element $\leq10^{16}$

No 2 consecutive entries in the array will be zero.

Sample Input

4
2 3 4 5
2
1 2 4
1 3 7

Sample Output

Yes
No

Source: hackerrank | Difficulty: MEDIUM
Tags: Number theory


Solutions:
import math
n = int(input())
a = list(map(int, input().split()))
nxt = [0] * (n + 1)
nxt[n] = n
for i in range(n - 1, -1, -1):
	if a[i] <= 1:
		nxt[i] = i
	else:
		nxt[i] = nxt[i + 1]
q = int(input())
LIM = 60
LOG_LIM = math.log(LIM * 2)

def bounded_pow(a, b):
	if b * math.log(a) > LOG_LIM:
		return LIM
	return min(pow(a, b), LIM)

def query(i, j, mod):
	if i == j or a[i] <= 1:
		return a[i] % mod == 0
	x = a[i]
	i += 1
	tmp = nxt[i]
	j = min(j, tmp)
	p = a[j]
	while j > i and p < LIM:
		j -= 1
		p = bounded_pow(a[j], p)
	return pow(x, p, mod) == 0
for _ in range(q):
	(i, j, mod) = map(int, input().split())
	i -= 1
	j -= 1
	print('Yes' if query(i, j, mod) else 'No')


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
INF = 1000000000
zero = [INF] * (N + 1)
one = [INF] * (N + 1)
for i in range(N - 2, -1, -1):
	zero[i] = i if A[i] == 0 else zero[i + 1]
	one[i] = i if A[i] == 1 else one[i + 1]

def pow(a, n, x):
	if n == 0:
		return 1
	half = pow(a, n // 2, x)
	if n % 2 == 0:
		return half * half % x
	else:
		return half * half * a % x

def check(i, j, x):
	if x == 1:
		return True
	if A[i] == 0:
		return True
	if A[i] == 1:
		return False
	if i == j:
		return A[i] % x == 0
	if j == i + 1:
		return pow(A[i], min(64, A[j]), x) == 0
	o = one[i]
	if o == i:
		return False
	else:
		assert o > i
		j = min(j, o - 1)
	z = zero[i]
	if z == i:
		return True
	elif z == i + 1:
		return False
	else:
		j = min(j, z - 2)
	p = 1
	for k in range(j, i, -1):
		p = A[k] ** p
		if p >= 64:
			p = 64
			break
	return pow(A[i], p, x) == 0
for q in range(Q):
	(i, j, x) = map(int, input().split())
	i -= 1
	j -= 1
	print('Yes' if check(i, j, x) else 'No')


import sys
import math

def read_int_line():
	a = list(map(int, input().split()))
	return a
ab = read_int_line()
N = ab[0]
A = read_int_line()
cd = read_int_line()
Q = cd[0]
ml = [1] * N
lln = [1] * 61
for i in range(N):
	if A[i] != 0:
		ml[i] = math.log(A[i])
for i in range(1, 60):
	lln[i] = math.log(i)

def check(i, j, mini):
	if i > j or A[i] == 1:
		return 1 >= mini
	if mini <= 0:
		return 1
	if A[i] == 0:
		return 0
	return check(i + 1, j, int(math.ceil(lln[mini] / ml[i])))

def expo(a, b, x):
	if b == 0:
		return 1
	y = expo(a, int(b / 2), x)
	if b % 2 == 1:
		return a * y % x * y % x
	return y * y % x
for k in range(Q):
	(i, j, x) = map(int, input().split())
	if x == 1:
		print('Yes')
		continue
	i = i - 1
	j = j - 1
	truc = 1
	b = A[i] % x
	res = 1
	pp = 0
	while 1:
		cur = b
		last = 1
		cpp = 1
		ok = 0
		while res * cur % x != 0 and pp + cpp // 2 < 54:
			last = cur
			cpp *= 2
			ok = 1
			cur = cur * cur % x
		res = res * last % x
		pp += cpp // 2
		if last == 1:
			break
	res = res * b % x
	pp += 1
	if res != 0:
		print('No')
	elif check(i + 1, j, pp) == 1:
		print('Yes')
	else:
		print('No')


n = int(input())
a = list(map(int, input().split()))

def f(x, y, z):
	if x == y:
		return a[x] >= z
	if z == 0:
		return True
	if a[x] == 0:
		return False
	if z == 1:
		return True
	if a[x] == 1:
		return False
	if a[x + 1] == 0:
		return False
	if a[x] >= z:
		return True
	(c, d) = (0, 1)
	while d < z:
		c += 1
		d *= a[x]
	return f(x + 1, y, c)
q = int(input())
for _ in range(q):
	ID = input().split()
	x = int(ID[0]) - 1
	y = int(ID[1]) - 1
	z = int(ID[2])
	if x == y:
		if a[x] % z == 0:
			print('Yes')
		else:
			print('No')
	else:
		c = 0
		d = 1
		if a[x] ** 54 % z != 0:
			print('No')
		else:
			while c < 54 and d % z != 0:
				c += 1
				d *= a[x]
			if c < 54 and f(x + 1, y, c):
				print('Yes')
			else:
				print('No')


import fractions
import bisect
import sys

def primeFactorsOfBincludedInA(a, b):
	pgcd = fractions.gcd(a, b)
	b = b // pgcd
	while pgcd != 1 and b != 1:
		pgcd = fractions.gcd(a, b)
		b = b // pgcd
	if b == 1:
		return True
	else:
		return False

def findPosFirstExp1(i, j):
	i0 = bisect.bisect_left(pos0s, i + 1)
	if i0 == len(pos0s):
		posFirst0 = j + 1
	else:
		posFirst0 = pos0s[i0]
	i1 = bisect.bisect_left(pos1s, i + 1)
	if i1 == len(pos1s):
		posFirst1 = j + 1
	else:
		posFirst1 = pos1s[i1]
	if posFirst0 <= j and posFirst0 <= posFirst1:
		return posFirst0 - 1
	elif posFirst1 <= j:
		return posFirst1
	else:
		return j + 1

def solve(i, j, x):
	a = A[i]
	if a == 0:
		return True
	if x == 1:
		return True
	if a == 1:
		return False
	if i + 1 <= j and A[i + 1] == 0:
		return False
	if a % x == 0:
		return True
	if not primeFactorsOfBincludedInA(a, x):
		return False
	exp = 1
	m = findPosFirstExp1(i, j)
	for k in range(m - 1, i, -1):
		exp = A[k] ** exp
		if pow(a, exp, x) == 0:
			return True
	return False
N = int(input())
A = list(map(int, input().split()))
pos0s = [i for i in range(len(A)) if A[i] == 0]
pos1s = [i for i in range(len(A)) if A[i] == 1]
Q = int(input())
for _ in range(Q):
	(i, j, x) = map(int, input().split())
	print('Yes' if solve(i - 1, j - 1, x) else 'No')


n = int(input())
A = list(map(int, input().split()))
q = int(input())

def bits(m, a):
	if m == 0:
		return 0
	return bits(m / a, a) + 1

def find(i, j, m):
	if m == 0:
		return 0
	if i > j:
		return 1
	if i == j:
		return min(55, A[i])
	if A[i] == 0:
		return 0
	if A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] >= 55:
		return 55
	return min(55, A[i] ** find(i + 1, j, m - 1))
ans = []
for qq in range(q):
	(i, j, x) = list(map(int, input().split()))
	i -= 1
	j -= 1
	if i > j:
		res = 1
	elif i == j or A[i] <= 1:
		res = A[i]
	else:
		res = pow(A[i], find(i + 1, j, 5), x)
	if res % x == 0:
		ans.append('Yes')
	else:
		ans.append('No')
for xx in range(len(ans)):
	print(ans[xx])


import sys
from time import time
from math import ceil, log

def find(aa, i, j):
	if i > j:
		return 1
	(u, v) = (aa[i], find(aa, i + 1, j))
	print('i=%d j=%d u=%d v=%d' % (i, j, u, v), file=sys.stderr)
	return pow(u, v)

def solve_bf(aa, i, j, x, _):
	print('aa=%s i=%d j=%d x=%d' % (aa, i, j, x), file=sys.stderr)
	u = find(aa, i, j)
	print('u=%d' % (u,), file=sys.stderr)
	return u % x == 0

def primes_gen(n):
	sieve = [True] * n
	for p in range(2, n):
		if sieve[p]:
			yield p
			for i in range(p + p, n, p):
				sieve[i] = False

def pfs_gen(n, prms):
	for p in prms:
		if p > n:
			break
		cnt = 0
		while n % p == 0:
			cnt += 1
			n //= p
		if cnt:
			yield (p, cnt)
	if n > 1:
		yield (n, 1)

def totient(n, prms):
	t = 1
	for (p, c) in pfs_gen(n, prms):
		t *= pow(p, c - 1) * (p - 1)
	return t

def tchain_gen(n, prms):
	if n == 1:
		yield 1
		return
	pfs = {p: c for (p, c) in pfs_gen(n, prms)}
	while pfs:
		(t, new_pfs) = (1, dict())
		for (p, c) in pfs.items():
			t *= pow(p, c - 1) * (p - 1)
			if c > 1:
				new_pfs[p] = c - 1
			for (u, v) in pfs_gen(p - 1, prms):
				if u in new_pfs:
					new_pfs[u] += v
				else:
					new_pfs[u] = v
		yield t
		pfs = new_pfs

def solve_slow(aa, i, j, x, prms):
	mm = (x,)
	mm += tuple(tchain_gen(x, prms))

	def calc(k, i, j):
		if k >= len(mm):
			return 0
		m = mm[k]
		a = aa[i]
		t = 1
		if k < len(mm) - 1:
			t = mm[k + 1]
		if m == 1:
			return 0
		if i == j:
			return a % m
		pwr = calc(k + 1, i + 1, j)
		return pow(a, pwr + t, m)
	u = calc(0, i, j)
	print('u=%d' % u, file=sys.stderr)
	return u == 0

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def same_pfs(a, b):
	return pow(a, 54, b) == 0

def solve(aa, i, j, x):
	print('i=%d j=%d x=%d' % (i, j, x), file=sys.stderr)
	if x == 1:
		return True
	a = aa[i]
	if a == 0:
		return True
	if a == 1:
		return False
	if not same_pfs(a, x):
		return False
	if i == j:
		return a % x == 0
	if aa[i + 1] == 0:
		return False
	mx_len = 6
	d = j - i
	l = min(d + 1, mx_len)
	pp = list()
	for k in range(i + 1, i + l):
		if aa[k] == 0:
			if pp:
				pp.pop()
			break
		if aa[k] == 1:
			break
		pp.append(aa[k])
		if len(pp) == d:
			break
	if not pp:
		return a % x == 0
	threshold = 54
	p = pp[-1]
	for k in range(len(pp) - 2, -1, -1):
		if p > threshold:
			break
		b = pp[k]
		l = log(threshold, b)
		if p > l:
			return True
		p = pow(b, p)
	print('a=%d p=%d' % (a, p), file=sys.stderr)
	return pow(a, p, x) == 0

def get_pfs(aa, prms):
	cache = list()
	for a in aa:
		cache.append(tuple(pfs_gen(a, prms)))
	return cache
tm = time()
N = pow(10, 6)
_ = int(input())
aa = tuple(map(int, input().split()))
q = int(input())
for _ in range(q):
	(i, j, x) = map(int, input().split())
	if solve(aa, i - 1, j - 1, x):
		print('Yes')
	else:
		print('No')
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


import math

def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	if a == 0:
		return b
	return gcd(b % a, a)
n = int(input())
a = list(map(int, input().strip().split()))
q = int(input())

def func2(i, j, x):
	if i == j:
		return a[i] >= x
	if x == 0:
		return True
	if a[i] == 0:
		return False
	if a[i] == 1:
		return x == 1
	if x == 1:
		return True
	k = 1
	while a[i] ** k < x:
		k += 1
	return func2(i + 1, j, k)

def func(i, j, x):
	if i == j:
		return a[i] % x == 0
	if x == 1:
		return True
	y = x
	rj = gcd(a[i], x)
	c = 0
	while rj != 1:
		y = y / rj
		rj = gcd(a[i], y)
		c += 1
	if y != 1:
		return False
	return func2(i + 1, j, c)
for _ in range(q):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if func(i, j, x):
		print('Yes')
	else:
		print('No')


def solve(i, j, step):
	if step == 0:
		return 0
	if i > j:
		return 1
	if i == j:
		return min(a[i], 55)
	if a[i] == 0:
		return 0
	if a[i] == 1 or a[i + 1] == 0:
		return 1
	if a[i] >= 55:
		return 55
	res = a[i] ** solve(i + 1, j, step - 1)
	res = min(res, 55)
	return res
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for qq in range(q):
	(i, j, x) = map(int, input().split())
	i = i - 1
	j = j - 1
	if i > j:
		ans = 1
	elif i == j or a[i] <= 1:
		ans = a[i]
	else:
		ans = int(pow(a[i], solve(i + 1, j, 5), x))
	print(['No', 'Yes'][ans % x == 0])


from math import log

def limit(a, x):
	if pow(a, 100, x) != 0:
		return -1
	k = 0
	b = 1
	while b != 0:
		b = b * a % x
		k += 1
	return k

def suptower(i, j, x):
	if i > j:
		return 1 >= x
	if A[i] <= 1:
		return A[i] >= x
	if A[i] >= x and (i == j or A[i + 1] > 0):
		return True
	return suptower(i + 1, j, log(x, A[i]))

def find(i, j, x):
	if x == 1:
		return True
	y = limit(A[i], x)
	if y < 0:
		return False
	return suptower(i + 1, j, y)

def main():
	global N, A
	N = int(input())
	A = list(map(int, input().split()))
	Q = int(input())
	for _ in range(Q):
		(i, j, x) = map(int, input().split())
		i -= 1
		j -= 1
		print('Yes' if find(i, j, x) else 'No')
main()


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if i == j:
		return min(max_exp, A[i])
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


from math import gcd

def check(i, j, x, A):
	if x == 1:
		return True
	y = A[i] % x
	if i == j:
		return y == 0
	if y == 0:
		return A[i + 1] != 0
	n = 1
	yn = y
	g = gcd(yn, x)
	while yn:
		n += 1
		yn = yn * y % x
		h = gcd(yn, x)
		if h == g:
			return False
		g = h
	for k in range(i + 1, j + 1):
		y = A[k]
		if y >= n and (n == 1 or k == j or A[k + 1] != 0):
			return True
		if y <= 1:
			return False
		m = n
		n = 1
		yn = y
		while yn < m:
			n += 1
			yn *= y
	return False
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
for q in range(Q):
	(i, j, x) = map(int, input().split())
	print('Yes' if check(i - 1, j - 1, x, A) else 'No')


import math

def gcd(a, b):
	if a > b:
		t = a
		a = b
		b = t
	while True:
		ba = b % a
		if ba == 0:
			return a
		(b, a) = (a, b % a)
(N, A, Q) = (int(input()), [int(x) for x in input().split(' ')], int(input()))
A.append(1)
ONE = [None] * N
p01 = N
FM = {}
for i in range(N - 1, 0, -1):
	if A[i + 1] == 0 or A[i] == 1:
		p01 == i
	if A[i + 1] == 0:
		FM[i] = A[i]
		A[i] = 1
	ONE[i] = p01
Y = 'Yes\n'
N = 'No\n'

def cmpFrom(i, j, t):
	if i > j:
		if t > 1.0:
			return N
		return Y
	if A[i] >= t:
		return Y
	if A[i] == 1:
		if t <= 1:
			return Y
		return N
	if A[i] == 0:
		return N
	return cmpFrom(i + 1, j, math.log(t, A[i]))
ES = {}
for i in range(2, 10000):
	if i in ES:
		continue
	e = 2
	ie = i * i
	while ie < 10 ** 16:
		ES[ie] = i
		ie *= i
		e += 1

def solution(i, j, x):
	i -= 1
	j -= 1
	if x == 1 or A[i] == 0:
		return Y
	Ai = A[i]
	if A[i + 1] == 0 and j < i:
		Ai = 1
	if Ai < 2:
		return N
	gx = x
	while True:
		g = gcd(gx, Ai)
		if g == 1:
			return N
		if g == gx:
			break
		gx = gx // g
	if gx in ES:
		gx = ES[gx]
	r = 0
	while Ai % gx == 0:
		Ai //= gx
		r += 1
	u = 0
	while x % gx == 0:
		x //= gx
		u += 1
	return cmpFrom(i + 1, min(j, ONE[i + 1]), u / r)
RS = ''
for q in range(Q):
	(i, j, x) = map(int, input().split(' '))
	fx = False
	if j - 1 in FM:
		A[j - 1] = FM[j - 1]
		fx = True
	RS += solution(i, j, x)
	if fx:
		A[j - 1] = 1
print(RS, end='')


import os, sys, math, datetime
from collections import Counter

def primes_list(n):
	a = [True] * (n + 1)
	a[0] = a[1] = False
	p = 2
	c = 0
	while p <= n:
		c += 1
		for i in range(p + p, n + 1, p):
			a[i] = False
		p += 1
		while p <= n and (not a[p]):
			p += 1
	return [i for i in range(2, n + 1) if a[i]]

def modular_power(a, n, m):
	if n == 0:
		return 1
	a = a % m
	if a < 0:
		a += m
	prod = 1
	pwr = a
	while n != 0:
		if n % 2 != 0:
			prod = prod * pwr % m
		n >>= 1
		if n == 0:
			break
		pwr = pwr * pwr % m
	return prod
MILLER_RABIN_CACHE = {}

def miller_rabin_cached(n):
	y = MILLER_RABIN_CACHE.get(n)
	if y is None:
		y = MILLER_RABIN_CACHE[n] = miller_rabin(n)
	return y

def miller_rabin(n):
	if n < 3825123056546413051:
		bases = [2, 3, 5, 7, 11, 13, 17, 19, 23]
	else:
		raise ValueError(n)
	prime_bases = [2, 3, 5, 7, 11, 13, 17, 19, 23]
	if n < 2:
		return False
	if n == 2 or n in prime_bases:
		return True
	if n % 2 == 0:
		return False
	(r, s) = (0, n - 1)
	while s % 2 == 0:
		r += 1
		s //= 2
	for a in bases:
		x = pow(a, s, n)
		if x == 1 or x == n - 1:
			continue
		for _ in range(r - 1):
			x = pow(x, 2, n)
			if x == n - 1:
				break
		else:
			return False
	return True
PRIMES = [None]
PF_CACHE2 = {}

def div_log(x, y, tableSize=1000000):
	if y % x == 0:
		return 1
	if modular_power(y, 64, x) != 0:
		return None
	(xorig, yorig) = (x, y)
	primes = PRIMES[0]
	if primes is None:
		primes = PRIMES[0] = primes_list(tableSize)
	counts = PF_CACHE2.get(x)
	ret = 1
	if counts is not None:
		for (p, c) in counts:
			c2 = 0
			while y != 0:
				(q, r) = divmod(y, p)
				if r != 0:
					break
				c2 += 1
				y = q
			if c2 == 0:
				return None
			ret = max(ret, iceil(c, c2))
	else:
		counts = Counter()
		primeTested = False
		pi = 0
		p = primes[pi]
		while x != 1:
			if p >= 1000000 and (not primeTested):
				if miller_rabin_cached(x):
					break
				primeTested = True
			c = 0
			while True:
				(q, r) = divmod(x, p)
				if r != 0:
					break
				c += 1
				x = q
			if c >= 1:
				counts[p] = c
				c2 = 0
				while y != 0:
					(q, r) = divmod(y, p)
					if r != 0:
						break
					c2 += 1
					y = q
				if c2 == 0:
					return None
				ret = max(ret, iceil(c, c2))
			if pi < len(primes) - 1:
				pi += 1
				p = primes[pi]
			else:
				p += 2
			if p * p > x:
				break
		if x != 1:
			counts[x] += 1
			if y % x != 0:
				ret = None
		PF_CACHE2[xorig] = list(sorted(counts.items()))
	return ret

def iceil(a, b):
	(q, r) = divmod(a, b)
	return q if r == 0 else q + 1

def solve(a, queries):
	a = [None] + a

	def is_ge(m, i, j):
		if i > j:
			return 1 >= m
		if m <= 0:
			return True
		if m <= 1:
			return a[i] >= 1
		ret = a[i] > 1 and is_ge(math.log(m) / math.log(a[i]), i + 1, j)
		return ret

	def solveOne(i, j, x):
		if i > j:
			return x == 1
		if a[i] == 0:
			return True
		if x == 1:
			return is_ge(1, i, j)
		lg = div_log(x, a[i])
		ret = lg is not None and is_ge(lg, i + 1, j)
		return ret

	def bstr(b):
		return 'Yes' if b else 'No'
	res = []
	for (qn, (i, j, x)) in enumerate(queries):
		res.append(bstr(solveOne(i, j, x)))
	return res
fptr = sys.stdout
a_count = int(input())
a = list(map(int, input().rstrip().split()))
q = int(input())
queries = []
for _ in range(q):
	queries.append(list(map(int, input().rstrip().split())))
result = solve(a, queries)
fptr.write('\n'.join(result))
fptr.write('\n')


import math

def gcd(a, b):
	if a > b:
		t = a
		a = b
		b = t
	while True:
		ba = b % a
		if ba == 0:
			return a
		(b, a) = (a, b % a)
(N, A, Q) = (int(input()), [int(x) for x in input().split(' ')], int(input()))
A.append(1)
ONE = [None] * N
p01 = N
FM = {}
for i in range(N - 1, 0, -1):
	if A[i + 1] == 0 or A[i] == 1:
		p01 == i
	if A[i + 1] == 0:
		FM[i] = A[i]
		A[i] = 1
	ONE[i] = p01
Y = 'Yes\n'
N = 'No\n'

def cmpFrom(i, j, t):
	if i > j:
		if t > 1.0:
			return N
		return Y
	if A[i] >= t:
		return Y
	if A[i] == 1:
		if t <= 1:
			return Y
		return N
	if A[i] == 0:
		return N
	return cmpFrom(i + 1, j, math.log(t, A[i]))
ES = {}
for i in range(2, 10000):
	if i in ES:
		continue
	e = 2
	ie = i * i
	while ie < 10 ** 16:
		ES[ie] = i
		ie *= i
		e += 1

def solution(i, j, x):
	i -= 1
	j -= 1
	if x == 1 or A[i] == 0:
		return Y
	Ai = A[i]
	if A[i + 1] == 0 and j < i:
		Ai = 1
	if Ai < 2:
		return N
	gx = x
	while True:
		g = gcd(gx, Ai)
		if g == 1:
			return N
		if g == gx:
			break
		gx = gx // g
	if gx in ES:
		gx = ES[gx]
	r = 0
	while Ai % gx == 0:
		Ai //= gx
		r += 1
	u = 0
	while x % gx == 0:
		x //= gx
		u += 1
	return cmpFrom(i + 1, min(j, ONE[i + 1]), u / r)
RS = ''
for q in range(Q):
	(i, j, x) = map(int, input().split(' '))
	fx = False
	if j - 1 in FM:
		A[j - 1] = FM[j - 1]
		fx = True
	RS += solution(i, j, x)
	if fx:
		A[j - 1] = 1
print(RS, end='')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import os
import sys
A = []

def Find(L, R, count):
	if count == 0:
		return 0
	if L > R:
		return 1
	if L == R:
		return min(55, A[L])
	if A[L] == 1 or A[L + 1] == 0:
		return 1
	if A[L] == 0:
		return 0
	if A[L] >= 55:
		return 55
	return min(55, A[L] ** Find(L + 1, R, count - 1))

def Solve(L, R, X):
	if L > R:
		return X == 1
	if L == R or A[L] < 2:
		return A[L] % X == 0
	return pow(A[L], Find(L + 1, R, 5), X) == 0
N = int(input())
A = list(map(int, input().split()))
T = int(input())
for i in range(T):
	(L, R, X) = map(int, input().split())
	L -= 1
	R -= 1
	print('Yes' if Solve(L, R, X) else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
n = int(input())
a = list(map(int, input().split()))
nxt = [0] * (n + 1)
nxt[n] = n
for i in range(n - 1, -1, -1):
	if a[i] <= 1:
		nxt[i] = i
	else:
		nxt[i] = nxt[i + 1]
q = int(input())
LIM = 60
LOG_LIM = math.log(LIM * 2)

def bounded_pow(a, b):
	if b * math.log(a) > LOG_LIM:
		return LIM
	return min(pow(a, b), LIM)

def query(i, j, mod):
	if i == j or a[i] <= 1:
		return a[i] % mod == 0
	x = a[i]
	i += 1
	tmp = nxt[i]
	j = min(j, tmp)
	p = a[j]
	while j > i and p < LIM:
		j -= 1
		p = bounded_pow(a[j], p)
	return pow(x, p, mod) == 0
for _ in range(q):
	(i, j, mod) = map(int, input().split())
	i -= 1
	j -= 1
	print('Yes' if query(i, j, mod) else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if i == j:
		return min(max_exp, A[i])
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')


import math
max_exp = math.ceil(math.log(10 ** 16) / math.log(2))

def find(i, j, n):
	if n == 0:
		return 0
	if i > j or A[i] == 1 or A[i + 1] == 0:
		return 1
	if A[i] == 0:
		return 0
	if A[i] >= max_exp:
		return max_exp
	return min(max_exp, A[i] ** find(i + 1, j, n - 1))
n = int(input())
A = list(map(int, input().strip().split()))
A.append(0)
for _ in range(int(input())):
	(i, j, x) = map(int, input().strip().split())
	i -= 1
	j -= 1
	if x == 1 or i > j:
		a = 1
	else:
		a = pow(A[i], find(i + 1, j, 4), x)
	print('Yes' if a % x == 0 else 'No')