给你一棵有根树,根位于顶点 1。每个顶点都涂上某种颜色。
如果没有其他颜色在顶点 v 的子树中出现的次数多于颜色 c,我们称颜色 c 在顶点 v 的子树中占主导地位。因此,有可能两种或多种颜色在某个顶点的子树中占主导地位。
顶点 v 的子树是顶点 v 以及到根的每条路径中包含顶点 v 的所有其他顶点。
对于每个顶点 v 求顶点 v 的子树中所有主颜色的总和。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 树中的顶点数。
第二行包含n个整数ci (1 ≤ ci ≤ n),ci — 第i个顶点的颜色。
接下来的 n - 1 行中的每一行都包含两个整数 xj, yj (1 ≤ xj, yj ≤ n) — 树的边缘。第一个顶点是树的根。
输出
打印 n 个整数 — 每个顶点的主颜色之和。
示例
输入 #1
4 1 2 3 4 1 2 2 3 2 4
输出 #1
10 9 3 4
输入 #2
15 1 2 3 1 2 3 3 1 1 3 2 2 1 2 3 1 2 1 3 1 4 1 14 1 15 2 5 2 6 2 7 3 8 3 9 3 10 4 11 4 12 4 13
输出 #2
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3