Given a tree rooted at node 1 and with n nodes, each having some integral value, you are asked to process two types of queries.
1iX: Update the value of node numbered i to X
2i : Find gcd of all the values of nodes in the subtree rooted at node i
Input
First line contains n and q as input. Next line contains n space separated integers denoting the value associated with each node. Next n−1 lines contain a pair of integer u,v denoting that there is an edge from node u to node v. Next q lines contain description of each query
Output
For each query of type 2 you have to output the required gcd value as asked in the query
Constraints
1≤n≤105
1≤u,v≤105
1≤nodevalue≤106
1≤q≤105
1≤X≤106
1≤i≤n