Given an Array of length  $N$  containing elements $Ai$ ( i = 1 to n ) . You have to handle $Q$ queries on this array . Each Query is of two types k=(1 or 2). 
Type 1:- $k$ $l$ $r$ in which you have to tell whether the product of numbers in range l to r results in a perfect square or not. if product of numbers in range $l$ to$r$ is a perfect square then simply output YES else output NO.
Type 2:- $k$ $i$ $val$ Multiply the value present at index $i$ with $val$.
Note#1: 1 based indexing in each query.
Note#2: Values of prime factors of all numbers $val$ and $Ai$ is between 2 to 100 only.

-----Input:-----
- First line will contain $N$, denoting the size of the array. Then the next line follow. 
- N integers  $Ai - An$.
- Third line will contain $Q$, denoting the number of queries. Then the next $Q$ lines follow -description of each query. 
- Each query consists of either type 1 or type 2 and each query gives you three elements either
-{$k$ $l$ $r$} or {$k$ $i$ $val$}

-----Output:-----
For each  Query of Type 1 Output either "YES" or "NO" Without Quotes.

-----Constraints-----
- $1 \leq N \leq 20000$
- $1 \leq Q \leq 20000$
- $2 \leq Ai \leq 1000000$
- $1 \leq i ,l,r \leq N$
- $1 \leq val \leq 1000000$
- $1 \leq l \leq r$

-----Subtasks-----
Subtask 1 :-40 points 
- Values of prime factors of all numbers $val$ and $Ai$ is between 2 to 40 only.
Subtask 2 :- 60 points
- Original Constraints 

-----Sample Input:-----
4
2 2 3 4
4
1 1 2
1 3 4
2 3 3
1 1 4

-----Sample Output:-----
YES
NO
YES

-----EXPLANATION:-----
-Query 1 :- product of numbers in range 1 to 2=2 * 2=4 (perfect square so YES)
-Query 2:- product of numbers in range 3 to 4 = 3 * 4 = 12 (not perfect square so NO)
-Query 3:- multiply number at index3 with 3 so number at index 3= 3*3 = 9 .
-Query 4:- product of numbers in range 1 to 4 = 2 * 2 * 9 * 4 = 144 (perfect square so YES)

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def update(index, value, bi_tree):
	while index < len(bi_tree):
		bi_tree[index] += value
		index += index & -index

def get_sum(index, bi_tree):
	ans = 0
	while index > 0:
		ans += bi_tree[index]
		index -= index & -index
	return ans

def get_range_sum(left, right, bi_tree):
	ans = get_sum(right, bi_tree) - get_sum(left - 1, bi_tree)
	return ans

def solve(x):
	s = set()
	res = 1
	i = 2
	while i * i <= x:
		count = 0
		while x % i == 0:
			x = x // i
			count += 1
		if count % 2:
			s.add(i)
		i += 1
	if x > 0:
		s.add(x)
	return s
n = int(input())
l = [0] + [int(i) for i in input().split()]
bit = [[0 for i in range(n + 1)] for i in range(101)]
for i in range(1, n + 1):
	s = solve(l[i])
	for j in s:
		update(i, 1, bit[j])
q = int(input())
for i in range(q):
	(k, a, b) = [int(i) for i in input().split()]
	if k == 1:
		f = 1
		for i in range(2, 100):
			res = get_range_sum(a, b, bit[i])
			if res % 2:
				f = 0
				break
		if f:
			print('YES')
		else:
			print('NO')
	else:
		s = solve(b)
		for j in s:
			update(a, 1, bit[j])