CF463E Caisa and Tree

给出 $n$ 个点，以 $1$ 为根的树，点 $u$ 有点权 $a_u$，$q$ 次操作，每次操作为以下两种中的一种： - `1 u`：查询点 $u$ 的一个最近祖先 $v$，使得 $\gcd(a_u,a_v)>1$，没有则输出 $-1$。 - `2 u d`：修改 $a_u$ 为 $d$。 其中，$2$ 操作次数不超过 $50$ 次。 $1\le n,m\le 10^5,1\le a_u\le 2\times10^6$

第一行两个正整数 $n$ 和 $q$。 第二行 $n$ 个正整数，表示点权。 之后的 $n-1$ 行，每行描述一条树上的边。 接下来的 $q$ 行，每行描述一个操作，格式和意义如上。 保证 $2$ 操作的数量不超过 $50$。

对于每个 $1$ 操作，输出答案。

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