← 返回题目列表

Codeforces · 842/C

C. 伊利亚和树

中文机器翻译题面 查看原题

Ilya 非常喜欢图表,尤其是树。在上次森林之旅中,伊利亚发现了一棵非常有趣的树,其根部位于顶点 1。树的每个顶点上都写有一个整数;写在顶点 i 上的数字等于 ai。

Ilya认为顶点x的美是从根到x的路径上写在顶点上的所有数字的最大公约数,包括这个顶点本身。此外,Ilya 可以将任意一个顶点的数字更改为 0 或保持所有顶点不变。现在,对于每个顶点,Ilya 想知道它可以拥有的最大可能的美感。

对于每个顶点,必须独立考虑答案。

根的美丽等于其上写的数字。

输入

第一行包含一个整数 n — 树中的顶点数 (1 ≤ n ≤ 2·105)。

下一行包含 n 个整数 ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 2·105)。

接下来的 n - 1 行中的每一行都包含两个整数 x 和 y (1 ≤ x, y ≤ n, x ≠ y),这意味着树中存在一条边 (x, y)。

输出

输出以空格分隔的 n 个数字,其中第 i 个数字等于顶点 i 的最大可能美度。

示例

输入 #1

2
6 2
1 2

输出 #1

6 6

输入 #2

3
6 2 3
1 2
1 3

输出 #2

6 6 6

输入 #3

1
10

输出 #3

10