角色属性树

题目描述

绪萌同人社是一个有趣的组织,该组织结构是一个树形结构。有一个社长,直接下属一些副社长。每个副社长又直接下属一些部长……。 每个成员都有一个萌点的属性,萌点属性是由一些质数的萌元素乘积构成(例如,猫耳的值是 $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$。

输入输出样例

输入样例 #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

说明

对于 $20\%$ 的数据,没有修改的操作。 对于 $50\%$ 的数据,$n\le 100$,修改次数 $<10$。 对于 $100\%$ 的数据,$n\le 200000$,$k<100000$,修改次数 $\le 50,a\_i\le 2^{31}-1$ UPD:本题测试数据随机,可能是假题。