E. Caisa and Treetime limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputCaisa 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(value of ui, value of v) > 1 and i < 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.InputThe 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.OutputFor each query of the first type output the result of the query.ExamplesInput4 610 8 4 31 22 33 41 11 21 31 42 1 91 4Output-112-11Notegcd(x, y) is greatest common divisor of two integers x and y.
Input4 610 8 4 31 22 33 41 11 21 31 42 1 91 4
Output-112-11
['brute force', 'dfs and similar', 'math', 'number theory', 'trees', '*2100']