Problem2688--Caisa and Tree

2688: Caisa and Tree

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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)>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.

Input

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.

Output

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

Examples
Input
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
Output
-1
1
2
-1
1
Note

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

Source/Category

 
[Submit] [Status]