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

凯萨现在在家，他的儿子给他布置了一个简单的任务。

给定一棵有 $n$ 个顶点的有根树，顶点编号为 $1$ 到 $n$（其中顶点 $1$ 为根）。树中每个顶点都有一个权值。你需要回答 $q$ 个查询，每个查询为以下两种类型之一：

• 查询格式为 "1 v"。设从根到顶点 $v$ 的路径上的顶点序列为 $u_1,\,u_2,\,\dots,\,u_k$（其中 $u_1 = 1$，$u_k = v$）。你需要输出一个顶点 $u_i$，使得 $\gcd(\text{顶点 } u_i \text{ 的权值},\ \text{顶点 } v \text{ 的权值}) > 1$，且 $i < k$。若存在多个满足条件的 $u_i$，则选择下标 $i$ 最大的那个。若不存在这样的顶点，则输出 $-1$。
• 查询格式为 "2 v w"。你需要将顶点 $v$ 的权值修改为 $w$。

你已获得全部查询，请帮助凯萨解决该问题。

The first line contains two space-separated integers n, q (1 ≤ n, q ≤ 105).

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 2·106), 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·106. Note that: there are no more than 50 queries that changes the value of a vertex.

第一行包含两个以空格分隔的整数 $n$、$q$（$1 ≤ n, q ≤ 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 2·10^6$），其中 $a_i$ 表示节点 $i$ 的值。

接下来的 $n - 1$ 行每行包含两个整数 $x_i$ 和 $y_i$（$1 ≤ x_i, y_i ≤ n$；$x_i ≠ y_i$），表示树中顶点 $x_i$ 与 $y_i$ 之间的边。

接下来的 $q$ 行每行包含一个如上所述格式的查询。对于每个查询，以下不等式成立：$1 ≤ v ≤ n$ 且 $1 ≤ w ≤ 2·10^6$。注意：修改节点值的查询不超过 50 个。

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

对于每条第一类查询，请输出该查询的结果。

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

$\gcd(x, y)$ 是两个整数 $x$ 和 $y$ 的最大公约数。