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: u1,u2,...,uk (u1=1;uk=v). You need to output such a vertex ui that gcd(valueofui,valueofv) \gt 1 and i \lt k. If there are several possible vertices ui 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 \le n,q \le 105).
The second line contains n integers a1,a2,...,an (1 \le ai \le 2 \cdot 106), where ai represent the value of node i.
Each of the next n-1 lines contains two integers xi and yi (1 \le xi,yi \le n;xi \neq 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 \le v \le n and 1 \le w \le 2 \cdot 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.
4 6 10 8 4 3 1 2 2 3 3 4 1 1 1 2 1 3 1 4 2 1 9 1 4· \n · · · \n · \n · \n · \n · \n · \n · \n · \n · · \n · \n
-1 1 2 -1 1\n \n \n \n \n
gcd(x,y) is greatest common divisor of two integers x and y.