O. Surgery on a Tree
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes, where each node has a strength of $$$a_i$$$.

You are asked to perform $$$q$$$ surgeries on the tree. Each surgery has an intensity of $$$k$$$. A surgery can be successfully performed if and only if it is possible to remove a (possibly empty) set of edges from the tree such that the strength of every resulting connected component is exactly $$$k$$$.

The strength of a connected component is defined as the sum of the strengths of all nodes within it.

For each of the $$$q$$$ surgeries, determine whether it can be performed. Note that the queries are independent; the tree is completely restored to its original state after evaluating each query.

Input

The first line contains one integer, $$$n \text{ } (1 \leq n \leq 10^6)$$$ — the number of nodes in the tree.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n \text{ }(0 \leq a_i \leq 10^{12})$$$ — the strength of each node on the tree.

Each of the next $$$n - 1$$$ lines contains two integers, $$$u \text{ } (1 \leq u \leq n)$$$ and $$$v \text{ }(1 \leq v \leq n)$$$, representing an edge connecting node $$$u$$$ and node $$$v$$$.

The next line contains one integer, $$$q \text{ } (1 \leq q \leq 10^6)$$$ — the number of surgeries you need to perform.

Each of the next $$$q$$$ lines contains one integer, $$$k \text{ } (0 \leq k \leq 10^{18})$$$ — the intensity of the surgery.

—

Tests $$$1$$$ — $$$4$$$ satisfy $$$n, q \leq 2000$$$.

Tests $$$5$$$ — $$$10$$$ satisfy $$$a_i \geq 1$$$.

Tests $$$11$$$ — $$$20$$$ satisfy no additional constraints.

Output

For each surgery, output YES if it can be performed, and NO otherwise.

Examples
Input
3
2 0 0
1 2
1 3
1
1
Output
NO
Input
8
0 4 2 2 4 0 4 4
1 2
1 3
3 4
1 5
1 6
6 7
6 8
6
4
10
5
20
2
8
Output
YES
NO
NO
YES
NO
NO
Note

For the first sample, the total strength of the tree is $$$2$$$.

  • $$$k = 1$$$ (NO): It is impossible to cut the tree into any components of strength $$$1$$$.

For the second sample, the total strength of the tree is $$$20$$$.

  • $$$k = 4$$$ (YES): Remove edges $$$(1,3)$$$, $$$(1,5)$$$, $$$(1,6)$$$, and $$$(6,8)$$$. The resulting components are $$$\{1, 2\}$$$, $$$\{3, 4\}$$$, $$$\{5\}$$$, $$$\{6, 7\}$$$, and $$$\{8\}$$$, each summing to exactly $$$4$$$. Note that $$$0$$$-weight nodes (like $$$1$$$ and $$$6$$$) must merge with other nodes.
  • $$$k = 10$$$ (NO): $$$10$$$ divides $$$20$$$, but it is structurally impossible to cut the tree into components of exactly $$$10$$$.
  • $$$k = 20$$$ (YES): Remove $$$0$$$ edges. The entire tree already sums to $$$20$$$.
  • $$$k \in \{2, 5, 8\}$$$ (NO): $$$8$$$ does not divide $$$20$$$. For $$$2$$$ and $$$5$$$, it is impossible to split individual nodes that already have a strength of $$$4$$$.