← 返回题目列表

Codeforces · 463/E

E. 凯萨和树

中文机器翻译题面 查看原题

Caisa 现在在家,他的儿子有一项简单的任务交给他。

给定一棵有 n 个顶点的有根树,编号从 1 到 n(顶点 1 是根)。树的每个顶点都有一个值。您应该回答 q 个问题。每个查询都是以下之一:

- 查询的格式为“1 v”。让我们写出从根到顶点 v 的路径上的顶点序列:u1, u2, ..., uk (u1 = 1; uk = v)。您需要输出这样的顶点 ui ,其 gcd(value of ui, value of v) > 1 且 i < k。如果有多个可能的顶点 ui,则选择 i 最大值的一个。如果没有这样的顶点输出-1。
- 查询的格式为“2 v w”。您必须将顶点 v 的值更改为 w。

您提出的所有疑问,请帮助财萨解决问题。

输入

第一行包含两个空格分隔的整数 n, q (1 ≤ n, q ≤ 105)。

第二行包含n个整数a1, a2, ..., an (1 ≤ ai ≤ 2·106),其中ai表示节点i的值。

接下来的 n - 1 行中的每一行都包含两个整数 xi 和 yi (1 ≤ xi, yi ≤ n; xi ≠ yi),表示顶点 xi 和 yi 之间的树的边。

接下来的 q 行中的每一行都包含一个采用上面给出的格式的查询。对于每个查询,以下不等式成立:1 ≤ v ≤ n 和 1 ≤ w ≤ 2·106。请注意:更改顶点值的查询不超过 50 个。

输出

对于第一种类型的每个查询,输出查询的结果。

示例

输入 #1

4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4

输出 #1

-1
1
2
-1
1

注意

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