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)

```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 = 'def update(index, value, bi_tree):\n while index < len(bi_tree):\n  bi_tree[index] += value\n  index += index & -index\n\n\ndef get_sum(index, bi_tree):\n ans = 0\n while index > 0:\n  ans += bi_tree[index]\n  index -= index & -index\n\n return ans\n\n\ndef get_range_sum(left, right, bi_tree):\n ans = get_sum(right, bi_tree) - get_sum(left - 1, bi_tree)\n return ans\n\n\ndef solve(x):\n s = set()\n res = 1\n i = 2\n while (i * i <= x):\n  count = 0\n  while (x % i == 0):\n   x = x // i\n   count += 1\n  if (count % 2):\n   s.add(i)\n  i += 1\n if (x > 0):\n  s.add(x)\n return s\n\n\nn = int(input())\nl = [0] + [int(i) for i in input().split()]\nbit = [[0 for i in range(n + 1)] for i in range(101)]\n\nfor i in range(1, n + 1):\n s = solve(l[i])\n for j in s:\n  update(i, 1, bit[j])\n\nq = int(input())\nfor i in range(q):\n k, a, b = [int(i) for i in input().split()]\n if (k == 1):\n  f = 1\n  for i in range(2, 100):\n   res = get_range_sum(a, b, bit[i])\n   if (res % 2):\n    f = 0\n    break\n  if (f):\n   print("YES")\n  else:\n   print("NO")\n else:\n  s = solve(b)\n  for j in s:\n   update(a, 1, bit[j])'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 20593