Ilya is very fond of graphs, especially trees. During his last trip to the forest Ilya found a very interesting tree rooted at vertex 1. There is an integer number written on each vertex of the tree; the number written on vertex _i_ is equal to _a__i_.
Ilya believes that the beauty of the vertex _x_ is the greatest common divisor of all numbers written on the vertices on the path from the root to _x_, including this vertex itself. In addition, Ilya can change the number in one arbitrary vertex to 0 or leave all vertices unchanged. Now for each vertex Ilya wants to know the maximum possible beauty it can have.
_For each vertex the answer must be considered independently._
_The beauty of the root equals to number written on it._
## Input
First line contains one integer number _n_ — the number of vertices in tree (1 ≤ _n_ ≤ 2·105).
Next line contains _n_ integer numbers _a__i_ (1 ≤ _i_ ≤ _n_, 1 ≤ _a__i_ ≤ 2·105).
Each of next _n_ - 1 lines contains two integer numbers _x_ and _y_ (1 ≤ _x_, _y_ ≤ _n_, _x_ ≠ _y_), which means that there is an edge (_x_, _y_) in the tree.
## Output
Output _n_ numbers separated by spaces, where _i_\-th number equals to maximum possible beauty of vertex _i_.
[samples]
Ilya 非常喜欢图，尤其是树。在他最近一次去森林的旅行中，Ilya 找到一棵以顶点 #cf_span[1] 为根的有趣树。树上的每个顶点上都写有一个整数，顶点 #cf_span[i] 上写的数是 #cf_span[ai]。
Ilya 认为顶点 #cf_span[x] 的美丽值是从根到 #cf_span[x] 的路径上所有顶点（包括 #cf_span[x] 自身）上所写数字的交错和。此外，Ilya 可以将任意一个顶点的数字改为 #cf_span[0]，或者保持所有顶点不变。现在，对于每个顶点，Ilya 想知道它所能达到的最大可能美丽值。
_每个顶点的答案必须独立考虑。_
_根的美丽值等于其上写的数字。_
第一行包含一个整数 #cf_span[n] —— 树中顶点的数量（#cf_span[1 ≤ n ≤ 2·105]）。
第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ i ≤ n]，#cf_span[1 ≤ ai ≤ 2·105]）。
接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[x ≠ y]），表示树中存在一条边 #cf_span[(x, y)]。
请输出 #cf_span[n] 个用空格分隔的数，其中第 #cf_span[i] 个数等于顶点 #cf_span[i] 的最大可能美丽值。
## Input
第一行包含一个整数 #cf_span[n] —— 树中顶点的数量（#cf_span[1 ≤ n ≤ 2·105]）。第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ i ≤ n]，#cf_span[1 ≤ ai ≤ 2·105]）。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[x ≠ y]），表示树中存在一条边 #cf_span[(x, y)]。
## Output
请输出 #cf_span[n] 个用空格分隔的数，其中第 #cf_span[i] 个数等于顶点 #cf_span[i] 的最大可能美丽值。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of vertices in a rooted tree, with root at vertex $ 1 $.
Let $ a = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the array of integers written on the vertices, where $ a_i $ is the value at vertex $ i $.
Let $ T = (V, E) $ be the tree with vertex set $ V = \{1, 2, \dots, n\} $ and edge set $ E $ of size $ n-1 $, rooted at vertex $ 1 $.
For each vertex $ x \in V $, let $ P(x) $ denote the set of vertices on the unique path from the root $ 1 $ to $ x $, inclusive.
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. $ 1 \leq a_i \leq 2 \cdot 10^5 $ for all $ i \in \{1, \dots, n\} $
3. The graph is a tree.
**Objective**
For each vertex $ x \in V $, define the *beauty* of $ x $ as:
$$
b(x) = \gcd\left( \{ a_v \mid v \in P(x) \} \right)
$$
Ilya may choose to set *at most one* vertex $ v \in V $ to $ 0 $ (or leave all unchanged), and the beauty is then computed over the resulting values (with $ \gcd(S \cup \{0\}) = \gcd(S) $ if $ S \neq \emptyset $, and $ \gcd(\{0\}) = 0 $).
For each vertex $ x $, compute the **maximum possible beauty** over all choices of at most one vertex to set to $ 0 $, **considering each vertex independently**.
That is, for each $ x \in V $, compute:
$$
\max_{S \subseteq P(x),\, |S| \leq 1} \gcd\left( \{ a_v \mid v \in P(x) \setminus S \} \right)
$$
where setting $ a_v = 0 $ for $ v \in S $ is equivalent to excluding $ a_v $ from the GCD computation.
**Note**: The GCD of an empty set is undefined, but since $ P(x) $ always contains the root, and we may remove at most one vertex, the set $ P(x) \setminus S $ is never empty.