Description

在一个平面上有n个齿轮，每个齿轮都有自己的初始半径\(r_i\)。有n-1对齿轮是互相嵌在一起的，即它们拥有相同的线速度。如果将n个齿轮当作n个点，将n-1条相嵌关系当作n-1条边，那么这些齿轮会组成一个树。即树上每条边连接的两个点代表的齿轮拥有相同的线速度。
现在有两种操作：
——操作1：将第x个齿轮的半径改成y
——操作2：如果给第x个齿轮一个角速度y，那么所有齿轮都旋转了起来，问所有齿轮中，角速度最大的是多少。
本题中，所有齿轮的半径以及角速度都是2的正整数次幂。
在此题中，你不需要考虑和某个齿轮嵌套的其它齿轮会发生冲突挤压。

Format

Input

第一行两个整数n,m(1<=n<=200000,1<=m<=200000)，分别表示齿轮的个数以及操作的个数。
第二行n个整数\(r_i\)，表示每个齿轮的初始半径。(1<=\(r_i\)<=\(2^{30}\)，且\(r_i\)=\(2^k\))
接下来n-1行，每行两个整数x,y，表示第x个齿轮与第y个齿轮具有相同的线速度。
接下来m行描述m个操作(op,x,y)
若op=1则表示操作1，将第x个齿轮的半径改成y(1<=y<=\(2^{30}\)，且y=\(2^k\))
若op=2则表示操作2，给第x个齿轮一个角速度y(1<=y<=\(2^{30}\)，且y=\(2^k\))

Output

对于每个操作2，输出最大的角速度。
数据保证最大的角速度一定是整数，但有可能会比较大，所以输出答案对\(10^9+7\)取模

Sample 1

Input

3 3
4 2 8
1 2
1 3
2 1 2
1 2 4
2 2 1

Output

4
1

Limitation

1s 256MB

Hint

对于操作1，第1个齿轮的角速度是2，第2个齿轮角速度是4，第3个齿轮角速度是1
对于操作3，第1个齿轮的角速度是1，第2个齿轮角速度是1，第3个齿轮角速度是\(\frac{1}{2}\)