角色属性树

题目描述

绪萌同人社是一个有趣的组织,该组织结构是一个树形结构。有一个社长,直接下属一些副社长。每个副社长又直接下属一些部长……。 每个成员都有一个萌点的属性,萌点属性是由一些质数的萌元素乘积构成(例如,猫耳的值是2,弱气的值是3,黄毛的值是5,病娇的值是7,双马尾的值是11等等) 举个例子,正妹是双份的猫耳,而且有一份弱气,她的属性值为2\*2\*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<=100,修改次数<10 对于100%的数据,n<=200000,k<100000 ,修改次数<=50,a\_i<=2^31-1 528