题目描述

绪萌同人社是一个有趣的组织，该组织结构是一个树形结构。有一个社长，直接下属一些副社长。每个副社长又直接下属一些部长……。

每个成员都有一个萌点的属性，萌点属性是由一些质数的萌元素乘积构成（例如，猫耳的值是 $2$，弱气的值是 $3$，黄毛的值是 $5$，病娇的值是 $7$，双马尾的值是 $11$ 等等）

举个例子，正妹是双份的猫耳，而且有一份弱气，她的属性值为 $2\times 2\times 3=12$。

现在组员关心一个问题，希望知道离自己最近且有相同萌元素上司是谁，例如，属性值为 $2、4、6、45$ 这样的属性值都算是和正妹有相同的属性。

然而，组员可能会随时变化自己的属性。啊。。感觉好麻烦啊。。

输入格式

第一行，$n,k$ 表示成员数与询问的次数

第二行，$n$ 个数，分别是 $1$ 到 $n$ 号成员的属性值

接下来 $n-1$ 行，$x_i,y_i$ 表示 $x_i$ 是 $y_i$ 的上司。

接下来来 $k$ 行，有两种情况

$1\ u_i$：询问离 $u_i$ 成员最近且有相同萌元素上司。

$2\ u_i$：$a$ 更改 $u_i$ 的属性值为 $a$。

输出格式

对于每个 $1$ 类型的询问，输出符合要求的编号。如果没有符合要求的编号，输出 $-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
2
-1
1

提示

对于 $20\%$ 的数据，没有修改的操作。

对于 $50\%$ 的数据，$n\le 100$，修改次数 $<10$。

对于 $100\%$ 的数据，$n\le 200000$，$k<100000$，修改次数 $\le 50,a\_i\le 2^{31}-1$

UPD：本题测试数据随机，可能是假题。