Problem E. Caisa and Tree

时间限制 10000 ms   内存限制 256 MB

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(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 vw". 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 ≤ 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 ≤ nxi ≠ 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.

输出数据

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

样例

样例说明

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

提交

请先 登录

© 2025 FAQs Contact About