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