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)

Difficulty: interview

Starter code:

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])