C. GCD on Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a tree$$$^{[6]}$$$ with $$$n$$$ vertices, where the $$$i$$$-th vertex is labeled with a positive integer $$$a_i$$$. A tree is eggy when the greatest common divisor of all its vertex-values is equal to $$$1$$$.

You have to process $$$q$$$ queries as follows:

  • $$$i\; x$$$: update the value of $$$i_{th}$$$ vertex by assigning $$$a_i = x$$$.
  • After each update, check if there's any edge in the tree that, when removed, splits the tree into two trees, where at least one of those trees is eggy.
Input

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — denoting the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — representing the values of the vertices.

Each of the following $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — denoting the indices of the vertices connected by an edge.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — representing the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$i$$$ and $$$x$$$ ($$$1 \le i \le n, 1 \le x \le 10^{18}$$$).

It is guaranteed that the given edges form a tree.

Output

After each query, print "YES" (without quotes) if there's any valid edge in the tree, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Examples
Input
2
2 2
1 2
4
1 3
2 1
1 2
2 2
Output
No
Yes
Yes
No
Input
3
6 2 3
1 2
1 3
5
2 6
1 2
1 3
3 5
3 6
Output
No
Yes
No
Yes
No