Finding the Nearest Similar Boss

The organization "Xumeng Fan Club" is structured as a tree. The president is at the root and each member has an attribute which is the product of several prime numbers (for example, cat ears = $2$, weak spirit = $3$, blonde hair = $5$, yandere = $7$, twin tails = $11$, etc.). For instance, a beauty might have the attribute $2\times2\times3 = 12$.

Two members are considered to have similar attributes if they share at least one common prime factor (i.e. if their greatest common divisor is more than $1$). Now, each member wants to know the closest boss (i.e. ancestor in the tree) whose attribute is similar to theirs. If no such boss exists on the chain from the member up to the president, output $-1$.

In addition, members may update their attribute at any time.

You are given the structure of the organization with the initial attributes and a sequence of queries. There are two types of queries:

1. Query (format: 1 u): For a given member $u$, find the closest boss (ancestor) having an attribute with at least one common prime factor with member $u$.

2. Update (format: 2 u val): Update the attribute of member $u$ to the new value $val$.

inputFormat

The first line contains two integers $n$ and $q$, representing the number of members and the number of queries, respectively.
The second line contains $n$ integers, the initial attribute values of the members from $1$ to $n$.
The next $n-1$ lines each contain one integer: for $i = 2$ to $n$, the $i$-th line gives the immediate boss of member $i$.
The following $q$ lines each contain a query in one of the following formats:\ • 1 u (Query: find the nearest boss for member $u$ with a similar attribute)\ • 2 u val (Update: change the attribute value of member $u$ to $val$)

outputFormat

For each query of type 1, output a single line containing the id of the closest boss with a similar attribute. Output $-1$ if no such boss exists.

sample

5 7
6 2 15 10 7
1
1
2
2
1 4
1 3
1 5
2 5 35
1 5
2 2 14
1 5

2
1
-1
-1
2