LCA
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一棵 n 个节点的魔法树，根节点为1，每个节点 i 有一个权值 a_i。

定义点 j 对点 i 是友好的，当且仅当 lca(i,j) 不等于 i 且不等于 j

对于节点 i ，存在集合 S(i)，S(i) 是所有对点 i 友好的点集的权值集合。

对于每个节点 i , 找到 gcd\{S(i)\}，空集合的 gcd 为 0

【名词解释】

1. lca(i,j)：两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。

2. gcd\{S(x)\}: 集合 S(x) 中所有数的 gcd

输入描述:

第一行输入一个整数n （1<=n<=3*10^5）代表这颗树节点的数量

第二行输入n个整数 a_1,a_2,...a_n (1<=a_i<=10^{12})，代表每个节点的权值

此后n-1行，第 i 行输入两个整数u_i,v_i （1<=u_i,v_i<=n）代表第 i 条树边连接 u_i 号节点和 v_i 号节点，保证输入的是一颗合法的树

输出描述:

在一行上输出 n 个整数，以空格分开，第 i 个整数表示节点 i 的 gcd\{S(i)\}
示例1

输入

复制 
5
8 3 3 5 8
4 3
2 4
5 3
1 3

输出

复制 
0 8 0 8 1
示例2

输入

复制 
5
7 6 4 5 10
1 2
2 3
1 4
1 5

输出

复制 
0 5 5 2 1