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.*;
import java.math.*;
public class codeforce{
    public static int n;
    public static long[] c;
    public static LinkedList<Integer>[] al;
    public static long[] sum;
    public static TreeMap<Long,Long>[] tb;
    public static TreeMap<Long,Long>[] ts;
    public static void dfs(int no,int p){
        int fis = 0;
        for(int x:al[no]){
            if(x==p) continue;
            fis++;
            dfs(x,no);
        }
        if(fis==0){
            tb[no] = new TreeMap<Long,Long>();
            ts[no] = new TreeMap<Long,Long>();
            tb[no].put(c[no],1L);
            ts[no].put(1L,c[no]);
            sum[no] = c[no];
            return;
        }
        int big = -1;
        int size = 0;
        for(int x:al[no]){
            if(x==p) continue;
            if(big==-1){
                big = x;
                size = tb[x].size()+ts[x].size();
            }else{
                int ns = tb[x].size()+ts[x].size();
                if(ns>size){
                    size = ns;
                    big = x;
                }
            }
        }
        tb[no] = tb[big];
        ts[no] = ts[big];
        tb[big] = null;
        ts[big] = null;
        for(int x:al[no]){
            if(x==p) continue;
            if(x==big) continue;
            for(Map.Entry<Long,Long>e:tb[x].entrySet()){
                long co = e.getKey();
                long nb = e.getValue();
                if(tb[no].containsKey(co)){
                    long nb2 = tb[no].get(co);
                    long d = ts[no].get(nb2);
                    d -= co;
                    if(d<=0) ts[no].remove(nb2);
                    else ts[no].put(nb2,d);
                    d = co;
                    if(ts[no].containsKey(nb+nb2)){
                        d += ts[no].get(nb+nb2);
                    }
                    ts[no].put(nb+nb2,d);
                    tb[no].put(co,nb+nb2);
                }else{
                    long d = co;
                    if(ts[no].containsKey(nb)){
                        d += ts[no].get(nb);
                    }
                    ts[no].put(nb,d);
                    tb[no].put(co,nb);
                }
            }
            tb[x].clear();
            tb[x] = null;
            ts[x].clear();
            ts[x] = null;
        }
        long co = c[no];
        long nb = 1L;
        if(tb[no].containsKey(co)){
            long nb2 = tb[no].get(co);
            long d = ts[no].get(nb2);
            d -= co;
            if(d<=0) ts[no].remove(nb2);
            else ts[no].put(nb2,d);
            d = co;
            if(ts[no].containsKey(nb+nb2)){
                d += ts[no].get(nb+nb2);
            }
            ts[no].put(nb+nb2,d);
            tb[no].put(co,nb+nb2);
        }else{
            long d = co;
            if(ts[no].containsKey(nb)){
                d += ts[no].get(nb);
            }
            ts[no].put(nb,d);
            tb[no].put(co,nb);
        }
        sum[no] = ts[no].get(ts[no].lastKey());
    }
    public static void main(String[] args)throws IOException{
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        sum = new long[n];
        c = new long[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) c[i] = Long.parseLong(st.nextToken());
        al = new LinkedList[n];
        for(int i=0;i<n;i++) al[i] = new LinkedList<Integer>();
        for(int i=1;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            al[x].add(y);
            al[y].add(x);
        }
        tb = new TreeMap[n];
        ts = new TreeMap[n];
        dfs(0,-1);
        out.print(sum[0]);
        for(int i=1;i<n;i++) out.print(" "+sum[i]);
        out.println("");
        out.flush();
   }
}