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.

Input

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.

Output

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

Note

$*gcd*(*x*, *y*)$ is greatest common divisor of two integers $*x*$ and $*y*$.