Description

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.

Input Format

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$.

Output Format

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

4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4

-1
1
2
-1
1

Hint

Constraints:

• For $20\%$ of the testdata, there are no update operations.
• For $50\%$ of the testdata, $n\le 100$, the number of updates $<10$.
• For $100\%$ of the testdata, $n\le 200000$, $k<100000$, the number of updates $\le 50$, and $a_i\le 2^{31}-1$.

UPD: The testdata are random; this might be a fake problem.

Translated by ChatGPT 5