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
// it will pass now
import java.io.*;
import java.util.*;
public class D {

    public static void main(String[] args) throws IOException {
//        Scanner sc = new Scanner(new FileReader("dream.in"));
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
//        int ttt = sc.nextInt();
//        int c = 1;
//        while (ttt-->0) {
            int n = sc.nextInt();
            int[] color = new int[n];
            for(int i=0;i<color.length;i++)color[i] = sc.nextInt();
            ArrayList<Integer>[] adjmat = new ArrayList[n];
            for (int i = 0; i < n; i++) adjmat[i] = new ArrayList<>();
            for (int i = 0; i < n - 1; i++) {
                int x = sc.nextInt() - 1;
                int y = sc.nextInt() - 1;
                adjmat[x].add(y);
                adjmat[y].add(x);
            }
            solve(adjmat,color);
            for(int i=0;i<n;i++)
                pw.print(result[i]+" ");
            pw.println();
//        }
        pw.flush();
        pw.close();
    }
    static int[] size;static long[] result;
    static ArrayList<Integer>[]S;
    static TreeMap<Integer,Node> tr;
    static HashMap<Integer,Integer>h;
    static int sz(ArrayList<Integer>[] adjmat,int a,int p){
        int res = 1;
        for(int u:adjmat[a]){
            if(u!=p)
                res+= sz(adjmat,u,a);
        }
        return size[a] = res;
    }
    static void solve(ArrayList<Integer>[] adjamt,int[] color){
        int n = adjamt.length;
        size = new int[n];
        result =new long[n];
        tr = new TreeMap<>();
        h = new HashMap<>();
        S = new ArrayList[n];
        tr.put(0,new Node());
        for(int i=0;i<n;i++){
            tr.get(0).add(color[i]);
            h.put(color[i],0);
        }
        sz(adjamt,0,-1);
        dfs(adjamt,0,-1,false,color);
    }
    static void dfs(ArrayList<Integer>[] adjamt,int a,int p,boolean keep,int[] color){
        int mx = -1;int big = -1;
        for(int u:adjamt[a]){
            if(u!=p && size[u]>mx){
                mx = size[u]; big = u;
            }
        }
        for(int u:adjamt[a]){
            if(u!=p &&u!=big){
                dfs(adjamt,u,a,false,color);
            }
        }
        if(big!=-1){
            dfs(adjamt,big,a,true,color);
            S[a] = S[big];
        }else{
            S[a] = new ArrayList<>();
        }
        S[a].add(a);
        int tt = h.getOrDefault(color[a],0);
        h.put(color[a],tt+1);
        tr.get(tt).remove(color[a]);
        if(tr.get(tt).sum==0)tr.remove(tt);
        if(!tr.containsKey(tt+1))tr.put(tt+1,new Node());
        tr.get(tt+1).add(color[a]);
        for(int u:adjamt[a]){
            if(u!=p && u!=big)
            for(int v:S[u]){
                int t = h.getOrDefault(color[v],0);
                h.put(color[v],t+1);
                tr.get(t).remove(color[v]);
                if(tr.get(t).sum==0)tr.remove(t);
                if(!tr.containsKey(t+1))tr.put(t+1,new Node());
                tr.get(t+1).add(color[v]);
                S[a].add(v);
            }
        }

        result[a] = tr.lastEntry().getValue().sum;
        if(!keep){
            for(int u:S[a]) {
                int tmp = h.get(color[u]);
                tr.get(tmp).remove(color[u]);
                if(tr.get(tmp).sum==0)tr.remove(tmp);
                h.put(color[u],tmp-1);
                if(!tr.containsKey(tmp-1))tr.put(tmp-1,new Node());
                tr.get(tmp-1).add(color[u]);
            }
        }
    }
    static class Node{
        TreeMap<Integer,Integer> tr;
        long sum;
        public Node(){
            tr = new TreeMap<>();
            sum = 0;
        }
        void add(int a){
            tr.put(a,tr.getOrDefault(a,0)+1);
            if(tr.getOrDefault(a,0)==1)
                sum+=a;
        }
        void remove(int a){
            tr.put(a,tr.getOrDefault(a,0)-1);
            if(tr.getOrDefault(a,0)==0)
                sum-=a;
        }
    }
    static class Scanner {
            StringTokenizer st;
            BufferedReader br;

            public Scanner(FileReader r) {
                br = new BufferedReader(r);
            }

            public Scanner(InputStream s) {
                br = new BufferedReader(new InputStreamReader(s));
            }

            public String next() throws IOException {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            }

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

            public long nextLong() throws IOException {
                return Long.parseLong(next());
            }

            public String nextLine() throws IOException {
                return br.readLine();
            }

            public double nextDouble() throws IOException {
                String x = next();
                StringBuilder sb = new StringBuilder("0");
                double res = 0, f = 1;
                boolean dec = false, neg = false;
                int start = 0;
                if (x.charAt(0) == '-') {
                    neg = true;
                    start++;
                }
                for (int i = start; i < x.length(); i++)
                    if (x.charAt(i) == '.') {
                        res = Long.parseLong(sb.toString());
                        sb = new StringBuilder("0");
                        dec = true;
                    } else {
                        sb.append(x.charAt(i));
                        if (dec)
                            f *= 10;
                    }
                res += Long.parseLong(sb.toString()) / f;
                return res * (neg ? -1 : 1);
            }

            public boolean ready() throws IOException {
                return br.ready();

            }
        }
}