No tag edit access

E. Caisa and Tree

time limit per test

10 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard 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*:*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.

Input

The first line contains two space-separated integers *n*, *q* (1 ≤ *n*, *q* ≤ 10^{5}).

The second line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 2·10^{6}), 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^{6}. 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*.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2017 23:12:54 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|