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
/**
 * Created by Aminul on 3/19/2018.
 */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class CF600E {
    static List<Integer> g[];
    static int start[], end[], time, color[], a[], BLOCK;
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt(); BLOCK = (int)Math.sqrt(n);
        initialize(n);
        for (int i = 1; i <= n; i++) {
            color[i] = in.nextInt();
        }
        for(int i = 0; i < n-1; i++){
            int u = in.nextInt(), v = in.nextInt();
            g[u].add(v);
            g[v].add(u);
        }

        dfs(1, -1);
        MO(pw, n);



        pw.close();
    }


    static void MO(PrintWriter pw, int q){
        Node [] pair = new Node[q];

        for(int i = 0; i < q; i++){
            pair[i] = new Node(start[i+1], end[i+1], i);
        }
        Arrays.sort(pair);

        long [] ans = new long[q];

        int maxCount[] = new int[q+1];
        long sum[] = new long[q+1];
        int freq[] = new int[q+1];
        int max = 0;

        int l = 1, r = 0, x = 0;

        for(int i = 0; i < q; i++){
            while( r < pair[i].v){
                r++;x = a[r];
                if(freq[x] > 0) {
                    maxCount[freq[x]]--;
                    sum[freq[x]] -= x;
                }
                freq[x]++;
                sum[freq[x]] += x;
                max = max(max, freq[x]);
                maxCount[freq[x]]++;
            }

            while( r > pair[i].v){
                x = a[r];
                if(freq[x] > 0) {
                    maxCount[freq[x]]--;
                    sum[freq[x]] -= x;
                }
                freq[x]--;
                sum[freq[x]] += x;
                r--;
                maxCount[freq[x]]++;
            }


            while( l > pair[i].u){
                l--;x = a[l];
                if(freq[x] > 0) {
                    maxCount[freq[x]]--;
                    sum[freq[x]] -= x;
                }
                freq[x]++;
                sum[freq[x]] += x;
                max = max(max, freq[x]);
                maxCount[freq[x]]++;
            }

            while( l < pair[i].u){
                x = a[l];
                if(freq[x] > 0) {
                    maxCount[freq[x]]--;
                    sum[freq[x]] -= x;
                }
                freq[x]--;
                sum[freq[x]] += x;
                l++;
                maxCount[freq[x]]++;
            }


            while (maxCount[max] == 0) max--;

            ans[pair[i].idx] = sum[max];
        }

        for(long i: ans) pw.print(i+" ");
        pw.println();
    }

    static class Node implements Comparable<Node>{
        public int u, v, idx;
        public Node(int uu, int vv, int i){
            u = uu; v = vv; idx = i;
        }
        public int compareTo(Node n){
            if(u/BLOCK != n.u/BLOCK) return u - n.u;
            else return v - n.v;
        }
    }

    static class SQRT_DECOM{

    }

    static void initialize(int n){
        g = intList(n+1);
        start = new int[n+1];
        end = new int[n+1];
        color = new int[n+1];
        a = new int[n+1];
    }

    static List<Integer>[] intList(int n){
        List<Integer> list[] = new List[n];
        for(int i = 0; i < n; i++) list[i] = new ArrayList<>();
        return list;
    }

    static void dfs(int u, int p){
        start[u] = ++time;
        a[time] = color[u];
        for(int v : g[u]){
            if(v != p) dfs(v, u);
        }
        end[u] = time;
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is){
            for(int i='0';i<='9';i++) ints[i]=i-'0';
            this.is = is;
        }

        public int readByte(){
            if(lenbuf == -1)throw new InputMismatchException();
            if(ptrbuf >= lenbuf){
                ptrbuf = 0;
                try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
                if(lenbuf <= 0)return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        public int skip() {
            int b;
            while((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        public String next(){
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt(){
            int num = 0, b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
       /* public char nextChar() {
            return (char)skip();
        }*/

        public char[] next(int n){
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while(p < n && !(isSpaceChar(b))){
                buf[p++] = (char)b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }
}