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 的最大公约数。