Caisa is now at home and his son has a simple task for him. Given a rooted tree with n vertices, numbered from 1 to n (vertex 1 is the root). Each vertex of the tree has a value. You should answer q queries. Each query is one of the following: Format of the query is "1 v ". Let's write out the sequence of vertices along the path from the root to vertex v : u 1, u 2, ..., u k (u 1 = 1; u k = v). You need to output such a vertex u i that gcd(value of u i , value of v) 1 and i k . If there are several possible vertices u i pick the one with maximum value of i . If there is no such vertex output -1. Format of the query is "2 v w ". You must change the value of vertex v to w . You are given all the queries, help Caisa to solve the problem.

输入描述:

The first line contains two space-separated integers n, q(1 ≤ n, q ≤ 105). The second line contains n integers a1, a2, ..., an(1 ≤ ai ≤ 2·106), where ai represent the value of node i.Each of the next n - 1 lines contains two integers xi and yi(1 ≤ xi, yi ≤ n; xi ≠ yi), denoting the edge of the tree between vertices xi and yi.Each of the next q lines contains a query in the format that is given above. For each query the following inequalities hold: 1 ≤ v ≤ n and 1 ≤ w ≤ 2·106. Note that: there are no more than 50 queries that changes the value of a vertex.

输出描述:

For each query of the first type output the result of the query.

备注:

gcd(x, y) is greatest common divisor of two integers x and y.