A9629 | Caisa and Tree

Caisa is now at home and his son has a simple task for him.

Given a rooted tree with $n$ vertices, numbered from $1$ to $n$ (vertex $1$ is the root). Each vertex of the tree has a value. You should answer $q$ queries. Each query is one of the following:

- Format of the query is "1 $v$ ". Let's write out the sequence of vertices along the path from the root to vertex $v$ : $u_{1},u_{2},...,u_{k}$ $(u_{1}=1; u_{k}=v)$ . You need to output such a vertex $u_{i}$ that $gcd(value of u_{i},value of v)>1$ and $i<k$ . If there are several possible vertices $u_{i}$ pick the one with maximum value of $i$ . If there is no such vertex output -1.
- Format of the query is "2 $v$ $w$ ". You must change the value of vertex $v$ to $w$ .

You are given all the queries, help Caisa to solve the problem.

The first line contains two space-separated integers $n$ , $q$ $(1<=n,q<=10^{5})$ .

The second line contains $n$ integers $a_{1},a_{2},...,a_{n}$ $(1<=a_{i}<=2·10^{6})$ , where $a_{i}$ represent the value of node $i$ .

Each of the next $n-1$ lines contains two integers $x_{i}$ and $y_{i}$ $(1<=x_{i},y_{i}<=n; x_{i}≠y_{i})$ , denoting the edge of the tree between vertices $x_{i}$ and $y_{i}$ .

Each of the next $q$ lines contains a query in the format that is given above. For each query the following inequalities hold: $1<=v<=n$ and $1<=w<=2·10^{6}$ . Note that: there are no more than $50$ queries that changes the value of a vertex.

For each query of the first type output the result of the query.