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
/*
    Refer to the DSU on Trees blog, and its explanation blog.
    Refer to https://codeforces.com/contest/600/submission/81916562
    
    col[i] stores the colour of vertex i.
    cnt[i] stores the number of vertices with colour i.
    size[i] stores the size of subtree of i.
    
    sum[i] stores the sum, if the max frequency was i.
    res[i] stores the answer for the subtree of i.
    
    edge[i] stores the vertices connected to i by an edge.
    subtree[i] stores all the vertices present in the subtree of i.
    
    preDFS calculates the subtree sizes.
    DFS calculates the results by performing small to large merging,
    thereby resulting in a complexity of only NlogN.
    
    How?
    Calculate the answers for all the light children, and then remove their 
    contribution. Then add the contribution of the heavy child, and 
    add the contribution of all other vertices present in the subtree of u.
    This is necessary to prevent over-counting and overlapping of answers.
    
    update adds the contribution of a vertex u. Then we update the max frequency
    accordingly.
    
    Pretty awesome technique.
 */

//created by Whiplash99
import java.io.*;
import java.util.*;
public class A
{
    private static ArrayDeque<Integer>[] edge,subtree;
    private static int[] col, cnt, size;
    private static long[] sum, res;

    private static void update(int u, int val)
    {
        sum[cnt[col[u]]]-=col[u];
        cnt[col[u]]+=val;
        sum[cnt[col[u]]]+=col[u];
    }
    private static int DFS(int u, int p, int keep) //Small to Large Merge
    {
        int max=0, bigChild=-1, bigSize=0;
        for(int v:edge[u]) //find the big child
        {
            if(v!=p&&size[v]>bigSize)
            {
                bigSize=size[v];
                bigChild=v;
            }
        }

        for(int v:edge[u]) //Find answers for the light children
        {
            if(v==p||v==bigChild) continue;
            DFS(v,u,0); //Don't add their contribution yet.
        }

        if(bigChild!=-1)
        {
            max = DFS(bigChild, u, 1);
            subtree[u]=subtree[bigChild];
        }

        update(u,1); //add colour of this node
        max=Math.max(max,cnt[col[u]]);
        subtree[u].add(u);

        for(int v:edge[u]) //add contribution of light children
        {
            if(v==p||v==bigChild) continue;
            for(int x:subtree[v])
            {
                update(x,1);
                max=Math.max(max,cnt[col[x]]);
                subtree[u].add(x);
            }
        }

        res[u]= sum[max]; //answer for vertex u.
        if(keep==0) //This is light child, remove contribution
        {
            for(int v:subtree[u])
                update(v,-1);
        }

        return max;
    }
    private static void preDFS(int u, int p) //DFS to get subtree sizes
    {
        size[u]=1;
        for(int v:edge[u])
        {
            if(v==p) continue;
            preDFS(v,u);
            size[u]+=size[v];
        }
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int i,N;

        N=Integer.parseInt(br.readLine().trim());

        cnt=new int[N+5]; col=new int[N+5]; size=new int[N+5];
        sum =new long[N+5]; res=new long[N+5];
        subtree=new ArrayDeque[N]; edge=new ArrayDeque[N];
        for(i=0;i<N;i++) edge[i]=new ArrayDeque<>();
        for(i=0;i<N;i++) subtree[i]=new ArrayDeque<>();

        String[] s=br.readLine().trim().split(" ");
        for(i=0;i<N;i++) col[i]=Integer.parseInt(s[i]);

        for(i=0;i<N-1;i++)
        {
            s=br.readLine().trim().split(" ");
            int u=Integer.parseInt(s[0])-1;
            int v=Integer.parseInt(s[1])-1;

            edge[u].add(v); edge[v].add(u);
        }

        preDFS(0,0);
        DFS(0,0,0);

        StringBuilder sb=new StringBuilder();
        for(i=0;i<N;i++) sb.append(res[i]).append(" ");

        System.out.println(sb);
    }
}