Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/25/2019 22:16:42 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|