I. Omar and Trees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

When Omar was at school, his teacher gave him a challenge, and Omar accepted it.

The teacher gave Omar a tree of $$$n$$$ nodes (node $$$1$$$ is the root). The $$$i_{th}$$$ node has a value $$$a_{i}$$$.

Then the teacher asked Omar $$$q$$$ queries of two types:

  • Update the value in every node in the subtree rooted with $$$u$$$ to $$$val$$$ ($$$u$$$ included).
  • Determine if the sum of all nodes in the subtree with root $$$u$$$ can be represented as the sum of two prime numbers or not ($$$u$$$ included).

Omar asks for your help in this challenge.

Input

The first line contains one integer $$$n$$$ $$$(1 \leq n \leq 10^{5})$$$.

The second line contains $$$n$$$ integers $$$(1\leq a_{i} \leq 10^{5})- $$$the value of each node.

For each $$$n-1$$$ lines, it contains two integers $$$u$$$ and $$$v$$$ $$$(1\leq u,v \leq n, u\ne v)-$$$ indices of nodes connected by an edge.

Then the number of queries $$$q$$$ $$$(1\leq q \leq 10^{5})$$$.

Each query format is one of the following:

  • $$$1$$$ $$$u$$$ $$$val$$$: Update the value in every node in the subtree rooted with $$$u$$$ to $$$val$$$ $$$(1\leq val \leq 10^{5})$$$.
  • $$$2$$$ $$$u$$$: Determine if the sum of all nodes in the subtree with root $$$u$$$ can be represented as the sum of two prime numbers or not.
Output

For each query of the second type, print "$$$YES$$$" without quotes if the sum of all nodes in the subtree with root $$$u$$$ can be represented as the sum of two prime numbers or not, "$$$NO$$$" without quotes otherwise.

Example
Input
9
3 5 2 7 10 6 1 4 3
1 2
2 3
1 4
4 5
5 6
4 7
7 8
7 9
6
2 7
2 2
1 7 10
2 7
1 7 9
2 7
Output
YES
YES
YES
NO