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
# dsu on tree
# logistics: if the problem asked to compute some value of a subtree
# naive method would be for each node, compute the query value which would be O(n^2) because of doing dfs for each node
# we want to reuse some information of subtree so that we do not need to recompute it
# we can use concept of heavy-light decomposition which we divide the value into light nodes and heavy node
# complexity proof:
from collections import defaultdict as df

from types import GeneratorType


def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to

    return wrappedfunc

timer = 0
@bootstrap
def dfs(v, p):
    global timer
    tin[v] = timer
    ver[timer] = v
    timer += 1

    for child in tree[v]:
        if child != p:
            yield dfs(child, v)
            size[v] += size[child]
    size[v] += 1
    tout[v] = timer
    timer += 1
    yield 0

def operation(mx, v, x):
    ans[cnt[color[v]]] -= color[v]
    cnt[color[v]] += x
    ans[cnt[color[v]]] += color[v]
    mx = max(mx, cnt[color[v]])
    return mx

@bootstrap
def dfs1(v, pa, keep):
    mx = 0;mx_child = -1; big_child = -1
    for child in tree[v]:
        if child != pa and size[child] > mx_child:
            mx_child = size[child]
            big_child = child
    for child in tree[v]:
        if child != pa and child != big_child:
            yield dfs1(child, v, 0)
    if big_child != -1:
        temp = yield dfs1(big_child, v, 1)
        mx = max(temp, mx)

    for child in tree[v]:
        if child != pa and child != big_child:
            for p in range(tin[child], tout[child]):
                # add operation
                #cnt[dist[ver[p]]] += 1
                mx = operation(mx, ver[p], 1)
    #add itself
    mx = operation(mx,v,1)
    #print(v,mx)
    res[v - 1] = ans[mx]
    #put answer above
    if not keep:
        for p in range(tin[v], tout[v]):
            # cancel operation
            #cnt[dist[ver[p]]] -= 1
            mx = operation(mx, ver[p], -1)
    yield mx

if __name__ == '__main__':

    n = int(input().strip())
    #arr = list(map(int, input().split()))
    color = [0] + list(map(int, input().split()))
    tree = df(list)
    for i in range(1,n):
        u,v = map(int, input().split())
        tree[u].append(v)
        tree[v].append(u)
        #tree[arr[i - 1]].append(i + 1)

    #maxn = 100000
    cnt = [0 for i in range(n + 1)]
    size = [0 for i in range(n + 1)]
    ver = [0 for i in range((n + 1) << 1)]
    tin = [0 for i in range(n + 1)]
    tout = [0 for i in range(n + 1)]
    ans = [0 for i in range(n + 1)]
    res = [0 for i in range(n)]
    #dist = [0 for i in range(n + 1)]

    # query = int(input().strip())
    # queries = df(list)
    # res = df(int)
    # for i in range(query):
    #     u, d = map(int, input().split())
    #     queries[u].append((d,i))
    dfs(1, 1)
    dfs1(1,1,1)
    #res[0] = ans
    print(' '.join(str(i) for i in res))
