F. A Perfect Path
time limit per test
1 s
memory limit per test
256 MB
input
standard input
output
standard output

There are $$$\mathbf{n}$$$ houses connected by $$$n - 1$$$ bidirectional roads, forming a tree. The houses are numbered from $$$1$$$ to $$$n$$$, and house $$$1$$$ is the root of the tree. Each house has an integer value $$$a_i$$$, which is called its house value.

You are given $$$q$$$ queries. In each query, you are given two houses $$$u$$$ and $$$v$$$. Your task is to determine whether the path from $$$u$$$ to $$$v$$$ is safe.

A path is considered safe if the product of all house values along the path from $$$u$$$ to $$$v$$$ is a perfect square.

A perfect square is a non-negative integer that can be expressed as the square of another integer (e.g., $$$0, 1, 4, 9, 16, 25, \ldots$$$). Negative numbers are not considered perfect squares.

Input

The first line contains a single integer $$$n$$$ $$$(2 \leq n \leq 2 \times 10^5)$$$ — the number of houses.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-2 \times 10^5 \leq a_i \leq 2 \times 10^5$$$) — the value of the i-th house.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, \,v \leq n, \, u \neq v)$$$ indicating a road between house $$$u$$$ and house $$$v$$$.

The next line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ $$$(1 \leq x, \, y \leq n)$$$ representing a query to check whether the path from house $$$x$$$ to house $$$y$$$ is safe or not.

Output

In each query, print Yes if the path is safe; print No otherwise.

Example
Input
7
1 4 1 -2 4 -2 -2
1 2
1 3
2 4
2 5
3 6
3 7
3
6 7
4 5
2 5
Output
Yes
No
Yes
Note
  • For $$$Query = 1$$$: The house value of the path from $$$6 \to 7$$$ are $$$\mathbf{-2, \, 1, \, -2}$$$ and product of them is $$$\mathbf{4}$$$. Which is a perfect square. So, the answer is Yes.
  • For $$$Query = 2$$$: The house value of the path from $$$4 \to 5$$$ are $$$\mathbf{-2, \, 4, \, 4}$$$ and product of them is $$$\mathbf{-32}$$$. Which is not a perfect square. So, the answer is No.
  • For $$$Query = 3$$$: The house value of the path from $$$2 \to 5$$$ are $$$\mathbf{4, \, 4}$$$ and product of them is $$$\mathbf{16}$$$. Which is a perfect square. So, the answer is Yes.