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₁,u₂,...,u_k (u₁=1;u_k=v). You need to output such a vertex u_i that gcd(valueofu_i,valueofv)>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≤10⁵).

The second line contains n integers a₁,a₂,...,a_n (1≤a_i≤2·10⁶), where a_i represent the value of node i.

Each of the next n-1 lines contains two integers x_i and y_i (1≤x_i,y_i≤n;x_i≠y_i), denoting the edge of the tree between vertices x_i and y_i.

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·10⁶. 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.