P2441 Character Attribute Tree

The Xumeng Fan Club is an interesting organization with a hierarchical tree structure. There is a president, who directly supervises several vice presidents. Each vice president, in turn, directly supervises several department heads, and so on. Each member has a "moe" attribute, which is the product of several prime "moe elements" (for example, the value of cat ears is $2$, timid is $3$, blonde is $5$, yandere is $7$, twin-tails is $11$, etc.). For example, suppose a certain member has double cat ears and one timid trait; then her attribute value is $2\times 2\times 3=12$. Now, members care about the following question: for themselves, who is the nearest superior that shares at least one common moe element? For example, attribute values $2, 4, 6, 45$ are all considered to share moe elements with the above member with attribute $12$. However, a member may change their attribute at any time. Ah... what a hassle.

The first line contains $n, k$, the number of members and the number of queries. The second line contains $n$ numbers, the attribute values of members $1$ through $n$. The next $n-1$ lines each contain $x_i, y_i$, meaning $x_i$ is the supervisor of $y_i$. Then $k$ lines follow, each of one of the two types: $1\ u_i$：Query the nearest superior of member $u_i$ that shares at least one moe element. $2\ u_i\ a$：Change the attribute value of $u_i$ to $a$.

For each type $1$ query, output the required member ID. If there is no such superior, output $-1$.

Constraints: - For $20\%$ of the testdata, there are no update operations. - For $50\%$ of the testdata, $n\le 100$, the number of updates $