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.*;
import java.util.Map.Entry;
public class Abc {
    static int c[];
    static ArrayList<Integer> adj[];
    static int n;
    static long ans[];
    static int sz[];
    static HashMap<Integer,Integer> map[];
    static int maxCnt[];
    public static void main(String[] args) throws Exception {
        FastReader sc = new FastReader();
        n=sc.nextInt();
        c=new int[n];
        adj=new ArrayList[n];
        map=new HashMap[n];
        maxCnt=new int[n];
        sz=new int[n];
        for (int i=0;i<n;i++){
            adj[i]=new ArrayList<>();
        }
        for (int i=0;i<n;i++)c[i]=sc.nextInt();
        for (int i=0;i<n-1;i++){
            int a=sc.nextInt()-1,b=sc.nextInt()-1;
            adj[a].add(b);
            adj[b].add(a);
        }
        ans=new long[n];
        dfs(0,-1);
        StringBuilder sb=new StringBuilder();
        for (long x:ans)sb.append(x+" ");
        System.out.println(sb);

    }
    static void dfs(int v, int par){
        int mx=-1,bigChild=-1;
        for (int u:adj[v]){
            if (u==par)continue;
            dfs(u,v);
            sz[v]+=sz[u];
            if (sz[u]>mx){
                mx=sz[u];
                bigChild=u;
            }
        }
        sz[v]++;
        if (bigChild==-1){
            map[v]=new HashMap<>();
        }else {
            ans[v]=ans[bigChild];
            maxCnt[v]=maxCnt[bigChild];
            map[v]=map[bigChild];
        }
        update(v,c[v],1);
        for (int u:adj[v]){
            if (u==par || u==bigChild)continue;
            for (Entry<Integer,Integer> e:map[u].entrySet()){
                update(v,e.getKey(),e.getValue());
            }
        }
    }
    static void update(int u,int val,int cnt){
        int occ=map[u].getOrDefault(val,0)+cnt;
        map[u].put(val,occ);
        if (occ==maxCnt[u]){
            ans[u]+=val;
        }else if (occ>maxCnt[u]){
            maxCnt[u]=occ;
            ans[u]=val;
        }
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}