ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5516: Caisa and Tree

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计Web Board

题目描述

E. Caisa and Tree
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.

输入样例 复制

输出样例 复制

分类标签