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

public class U {

    static ArrayList<Integer>[]g ;
    static long[]sol ;
    static int[] a,maxn;
    static HashMap<Integer,Integer>[]sets;
    static void dfs(int u ,int p ){
        long ans =a[u];
        int max=maxn[u];
        for (int v:g[u]){
            if (v!=p){
                dfs(v,u);
                if (sets[u].size()>=sets[v].size()){
                    for (int k:sets[v].keySet()){
                        sets[u].put(k,sets[v].get(k)+sets[u].getOrDefault(k,0));
                        if (sets[u].get(k)>max){
                            max=sets[u].get(k);
                            ans=k;
                        }
                        else {
                            if (sets[u].get(k)==max){
                                ans+=k;
                            }
                        }
                    }
                }
                else {
                    if (maxn[u]<maxn[v]){
                        max=maxn[v];
                        ans=sol[v];
                    }
                    else {
                        if (maxn[u]==maxn[v]){
                            max=maxn[u];
                            ans=sol[v];
                        }
                    }
                    for (int k:sets[u].keySet()){
                        sets[v].put(k,sets[u].get(k)+sets[v].getOrDefault(k,0));
                        if (sets[v].get(k)>max){
                            max=sets[v].get(k);
                            ans=k;
                        }
                        else {
                            if (sets[v].get(k)==max){
                                ans+=k;
                            }
                        }
                    }
                    sets[u]=sets[v];
                }
            }
        }
        maxn[u]=max;
        sol[u]=ans;
    }
    public static void main(String[]args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        g = new ArrayList[n];
        maxn= new int[n];
        Arrays.fill(maxn,1);
        sets = new HashMap[n];
        for (int i =0;i<n;i++){
            sets[i]= new HashMap<>();
            g[i]= new ArrayList<>();
        }
        a= new int[n];
        for (int i =0;i<n;i++){
            a[i]=sc.nextInt();
            sets[i].put(a[i],1);
        }
        for (int i =0;i<n-1;i++){
            int u = sc.nextInt()-1;
            int v = sc.nextInt()-1;
            g[u].add(v);
            g[v].add(u);
        }
        sol = new long[n];
        dfs(0,-1);
        for (int i =0;i<n;i++){
            pw.print(sol[i]);
            pw.print(" ");
        }
        pw.flush();
    }
    static  class  DSU{
        int [] p,size;
        public DSU(int n){
            p= new int[n];
            size= new int[n];
            for (int i =0;i<n;i++){
                p[i]=i;
                size[i]=1;
            }
        }
        int findSet(int i){
            return ( p[i]!=i?p[i]=findSet(p[i]):i);
        }
        boolean sameSet(int i, int j){
            return findSet(i)==findSet(j);
        }
        void union(int i ,int j){
            if (sameSet(i,j))return;
            int x=findSet(i);
            int y=findSet(j);
            if (size[x]>size[y]){
                p[y]=x;
                size[x]+=size[y];
            }
            else {
                p[x]=y;
                size[y]+=size[x];
            }
        }
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        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();
        }

    }

}
