You are given a rooted tree with root in vertex 1. Each vertex is coloured in some colour.

Let's call colour c dominating in the subtree of vertex v if there are no other colours that appear in the subtree of vertex v more times than colour c. So it's possible that two or more colours will be dominating in the subtree of some vertex.

The subtree of vertex v is the vertex v and all other vertices that contains vertex v in each path to the root.

For each vertex v find the sum of all dominating colours in the subtree of vertex v.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of vertices in the tree.

The second line contains n integers ci (1 ≤ ci ≤ n), ci — the colour of the i-th vertex.

Each of the next n - 1 lines contains two integers xj, yj (1 ≤ xj, yj ≤ n) — the edge of the tree. The first vertex is the root of the tree.

Output

Print n integers — the sums of dominating colours for each vertex.

Examples

Input

4
1 2 3 4
1 2
2 3
2 4


Output

10 9 3 4


Input

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


Output

6 5 4 3 2 3 3 1 1 3 2 2 1 2 3
import sys
input = sys.stdin.buffer.readline
 
 
class SegmentTree:
    def __init__(self, n, op, e):
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)
 
    def __getitem__(self, i):
        return self.node[i + self.size]
 
    def __setitem__(self, i, val):
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
    def build(self, array):
        for i, val in enumerate(array, self.size):
            self.node[i] = val
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
    def all_fold(self):
        return self.node[1]
 
    def fold(self, l, r):
        l, r = l + self.size, r + self.size
        vl, vr = self.e, self.e
        while l < r:
            if l & 1:
                vl = self.op(vl, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.op(self.node[r], vr)
            l, r = l >> 1, r >> 1
        return self.op(vl, vr)
 
 
def topological_sorted(tree, root=None):
    n = len(tree)
    par = [-1] * n
    tp_order = []
    for v in range(n):
        if par[v] != -1 or (root is not None and v != root):
            continue
        stack = [v]
        while stack:
            v = stack.pop()
            tp_order.append(v)
            for nxt_v in tree[v]:
                if nxt_v == par[v]:
                    continue
                par[nxt_v] = v
                stack.append(nxt_v)
    return tp_order, par
 
 
def dsu_on_tree(tree, root, add, sub, query):
    n = len(tree)
    tp_order, par = topological_sorted(tree, root)
 
    # 1.有向木の構築
    di_tree = [[] for i in range(n)]
    for v in range(n):
        for nxt_v in tree[v]:
            if nxt_v == par[v]:
                continue
            di_tree[v].append(nxt_v)

    # 2.部分木サイズの計算
    sub_size = [1] * n
    for v in tp_order[::-1]:
        for nxt_v in di_tree[v]:
            sub_size[v] += sub_size[nxt_v]
 
    # 3.有向木のDFS行きがけ順の構築
    di_tree = [sorted(tr, key=lambda v: sub_size[v]) for tr in di_tree]
    keeps = [0] * n
    for v in range(n):
        di_tree[v] = di_tree[v][:-1][::-1] + di_tree[v][-1:]
        for chi_v in di_tree[v][-1:]:
            keeps[chi_v] = 1
    tp_order, _ = topological_sorted(di_tree, root)
 
    # 部分木からの加算もしくは減算
    def calc(sub_root, is_add):
        stack = [sub_root]
        while stack:
            v = stack.pop()
            add(v) if is_add else sub(v)
            for chi_v in di_tree[v]:
                stack.append(chi_v)

    # 4.有向木のDFS帰りがけ順で頂点vの部分木クエリを処理
    for v in tp_order[::-1]:
        for chi_v in di_tree[v]:
            if keeps[chi_v] == 0:
                calc(chi_v, 1)
        add(v)
        # ここでクエリを実行する
        query(v)
        if keeps[v] == 0:
            calc(v, 0)


n = int(input())
colors = list(map(int, input().split()))
edges = [list(map(int, input().split())) for i in range(n - 1)]


tree = [[] for i in range(n)]
for u, v in edges:
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)

def op(x, y):
    # x = (max, sum_val)
    if x[0] == y[0]:
        return x[0], x[1] + y[1]
    elif x[0] > y[0]:
        return x
    elif x[0] < y[0]:
        return y

e = (0, 0)
st = SegmentTree(10 ** 5 + 10, op, e)
st.build([(0, i) for i in range(10 ** 5 + 10)])

def add(v):
    max_, sum_ = st[colors[v]]
    st[colors[v]] = (max_ + 1, sum_)

def sub(v):
    max_, sum_ = st[colors[v]]
    st[colors[v]] = (max_ - 1, sum_)

ans = [0] * n
def query(v):
    max_, sum_ = st.all_fold()
    ans[v] = sum_

dsu_on_tree(tree, 0, add, sub, query)
print(*ans)