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.BigInteger;
import java.text.*;

public class Main{
    static final long MOD = (long)1e9+7, IINF = (long)1e19;
    static final int MAX = (int)1e5+1, MX = (int)65e5+1, INF = (int)1e9, B = 18;
    static final double EPS = 1e-8;
    static FastReader in;
    static PrintWriter out;
    static boolean multipleTC = false;
    static DecimalFormat df = new DecimalFormat("0.0000000");
    static String file = "C:/users/user/desktop/code/C-large-practice";
    public static void main(String[] args) throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
//            in = new FastReader(file+".in");
//            out = new PrintWriter(file+".out");
        for(int i = 1, t = (multipleTC)?ni():1; i<=t; i++)solve(i);
        out.flush();
        out.close();
    }
    
    static int n,sz[], col[];
    static ArrayList<Integer>[] adj;
    static void solve(int TC){
        n = ni();
        adj = new ArrayList[n];
        col = ia(n);sz = new int[n];
        for(int i = 0; i< n; i++)adj[i] = new ArrayList<>();
        for(int i = 1; i< n; i++){
            int u = ni()-1, v = ni()-1;
            adj[u].add(v);
            adj[v].add(u);
        }
        a = new MySet[n];ans = new long[n];
//        size(0, -1);
        dfs(0, -1);
        for(long l:ans)p(l+" ");
    }
    
    static long[] ans;
    static MySet[] a;
    static void dfs(int u, int p){
        int mx = 0, b = -1;
        for(int v:adj[u]){
            if(v==p)continue;
            dfs(v,u);
            if(sz[v]>mx){
                mx = sz[v];
                b = v;
            }
        }
        sz[u] = 1+mx;
        if(b == -1){
            a[u] = new  MySet();
            a[u].add(col[u], 1);
        }else{
            a[u] = a[b];
            a[u].add(col[u], 1);
            for(int v:adj[u]){
                if(v==p || v== b)continue;
                sz[u]+=sz[v];
                for(Map.Entry<Integer, Integer> e:a[v].map.entrySet())a[u].add(e.getKey(), e.getValue());
            }
        }
        ans[u] = a[u].sum;
    }
    
    static class MySet{
        TreeSet<Integer> s;
        int fre = 0;
        long sum = 0;
        HashMap<Integer, Integer> map;
        public MySet(){
            s = new TreeSet<>();
            map = new HashMap<>();
        }
        public void add(int i, int fr){
            int g = map.getOrDefault(i,0)+fr;
            map.put(i, g);
            if(g>fre){
                s = new TreeSet<>();
                fre = g;
                s.add(i);
                sum = i;
            }else if(g == fre){
                if(!s.contains(i)){
                    s.add(i);
                    sum+=i;
                }
            }
        }
    }
    
    static long modPow(long a, long p){
        long o = 1;
        while(p>0){
            if(p%2==1)o = (a*o)%MOD;
            p/=2;
            a = (a*a)%MOD;
        }
        return o;
    }

    static int[] ia(int n){
        int[] out = new int[n];
        for(int i = 0; i< n; i++)out[i] = ni();
        return out;
    }

    static long[] la(int n){
        long[] out = new long[n];
        for(int i = 0; i< n; i++)out[i] = nl();
        return out;
    }

    static long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    static int bitcount(long n){return (n==0)?0:(1+bitcount(n&(n-1)));}
    static void p(Object o){out.print(o);}
    static void pn(Object o){out.println(o);}
    static void pni(Object o){out.println(o);out.flush();}
    static String n(){return in.next();}
    static String nln(){return in.nextLine();}
    static int ni(){return Integer.parseInt(in.next());}
    static long nl(){return Long.parseLong(in.next());}
    static double nd(){return Double.parseDouble(in.next());}

    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

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

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