Subtree Queries

5

5 votes
Medium
Problem

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 n1 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
1n105
1u,v105
1nodevalue106
1q105
1X106
1in

Sample Input
2 2
6 12
1 2
2 1 
2 2
Sample Output
6
12
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?