SOLVE
LATER
You are given a tree with $$N$$ nodes. Each node $$x$$ has a value $$V_x$$ associated with it.
You will also be given $$Q$$ queries of two types:
0 a x
: Set $$V_a$$ to $$x$$1 a b c
: Find number of nodes on the unique path from $$a$$ to $$b$$ with value $$v$$ such that $$gcd(v, c) = 1$$Input Format:
The first line contains two integers, $$N$$ and $$Q$$
The second line contains $$N$$ space separated integers, where the $$i^{th}$$ of them represents the value of node $$i$$.
Next $$N - 1$$ lines contain two integers $$a$$ and $$b$$, denoting that there is an undirected edge between nodes $$a$$ and $$b$$.
Next $$Q$$ lines contains a query in either of the above two formats.
Constraints:
$$1 \le N, Q \le 10^5$$
$$1 \le v \le 5000$$ where v is the value of any node at any given time
For query of type 0
, $$1 \le a \le N$$ and $$1 \le x \le 5000$$
For query of type 1
, $$1 \le a, b \le N$$ and $$1 \le c \le 5000$$
Output Format:
For each query of the second type, output as answer a single integer denoting the answer to that query.
Note: It is recommended to use faster I/O methods.
For the first query, the values on the path are 1, 2, 3. Here 1, 3 have gcd equal to 1 with 2.
The third query updates node 1's value to 2.
For the fourth query, the values now are 2, 2, 3. Here only 3 has gcd equal to 1 with 2.