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 java.util.*;
import java.io.*;

public class E {

    static int n;
    static int[] c;
    static ArrayList<ArrayList<Integer>> e;
    static ArrayList<Map<Integer, Integer>> m;
    static long[] mnum;
    static long[] s;


    public static void dfs(int cur, int pre)
    {
        int mar = -1;
        for (int r : e.get(cur)) if (r != pre)
        {
            dfs(r, cur);
            if (mar == -1 || m.get(r).size() > m.get(mar).size())
                mar = r;
        }
        if (mar != -1)
        {
            Map<Integer, Integer> tmp = m.get(cur);
            m.set(cur, m.get(mar));
            m.set(mar, tmp);
            mnum[cur] = mnum[mar];
            s[cur] = s[mar];
        }
        for (int r : e.get(cur)) if (r != pre)
        {
            Map<Integer, Integer> rmap = m.get(r);
            for (int k : rmap.keySet())
            {
                if (!m.get(cur).containsKey(k))
                    m.get(cur).put(k, 0);
                int curval = m.get(cur).get(k) + rmap.get(k);
                m.get(cur).put(k, curval);
                if (curval > mnum[cur])
                {
                    mnum[cur] = curval;
                    s[cur] = 0;
                }
                if (curval == mnum[cur])
                    s[cur] += k;
            }
        }
        if (!m.get(cur).containsKey(c[cur]))
            m.get(cur).put(c[cur], 0);
        int curcval = m.get(cur).get(c[cur]) + 1;
        m.get(cur).put(c[cur], curcval);
        if (curcval > mnum[cur])
        {
            mnum[cur] = curcval;
            s[cur] = 0;
        }
        if (curcval == mnum[cur])
            s[cur] += c[cur];
    }

    public static void main(String[] args)
    {
        QuickScanner in = new QuickScanner(System.in);
        n = in.nextInt();
        c = new int[n];
        e = new ArrayList<ArrayList<Integer>>(n);
        m = new ArrayList<Map<Integer, Integer>>(n);
        mnum = new long[n];
        s = new long[n];
        for (int i = 0; i < n; i++)
        {
            c[i] = in.nextInt();
            e.add(new ArrayList<Integer>());
            m.add(new HashMap<Integer, Integer>());
        }
        for (int i = 0; i < n - 1; i++)
        {
            int x = in.nextInt()-1;
            int y = in.nextInt()-1;
            e.get(x).add(y);
            e.get(y).add(x);
        }
        E.dfs(0, -1);

        for (int i = 0; i < n; i++)
            System.out.print(s[i] + " ");
        System.out.println();
    }
}



































class QuickScanner {
    BufferedReader in;
    StringTokenizer token;
    String delim;
    public QuickScanner(InputStream inputStream)
    {
        this.in=new BufferedReader(new InputStreamReader(inputStream));
        this.delim=" \n\t";
        this.token=new StringTokenizer("",delim);
    }

    public boolean hasNext()
    {
        while(!token.hasMoreTokens())
        {
            try {
                String s=in.readLine();
                if(s==null) return false;
                token=new StringTokenizer(s,delim);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
        }
        return true;
    }

    public String next()
    {
        hasNext();
        return token.nextToken();
    }

    public int nextInt()
    {
        return Integer.parseInt(next());
    }

}
