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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author FinnTheHuman
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        int n;
        int[] color;
        int[] from;
        int[] to;
        int[] flatten;
        ArrayList<Integer>[] g;
        int cur;
        int[] freqMap;
        long[] freqSum;
        int maxFreq;

        void dfs(int u, int par) {
            flatten[cur] = u;
            from[u] = cur;
            for (int adj : g[u]) {
                if (adj != par) {
                    ++cur;
                    dfs(adj, u);
                }
            }
            to[u] = cur;
        }

        public int get(int u) {
            return freqMap[u];
        }

        public void add(int u) {
            int oldFreq = get(u);
            freqSum[oldFreq] -= (long) u;
            freqSum[oldFreq + 1] += (long) u;
            if (oldFreq + 1 > maxFreq) maxFreq = oldFreq + 1;
            ++freqMap[u];
        }

        public void remove(int u) {
            int oldFreq = get(u);
            freqSum[oldFreq] -= (long) u;
            freqSum[oldFreq - 1] += (long) u;
            if (freqSum[maxFreq] == 0) --maxFreq;
            --freqMap[u];
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            g = new ArrayList[n + 1];
            for (int i = 0; i < n; ++i) g[i] = new ArrayList<>();
            color = new int[n + 1];
            for (int i = 0; i < n; ++i) color[i] = in.nextInt();
            for (int i = 1; i < n; ++i) {
                int u = in.nextInt() - 1;
                int v = in.nextInt() - 1;
                g[u].add(v);
                g[v].add(u);
            }
            from = new int[n + 1];
            to = new int[n + 1];
            flatten = new int[n + 1];
            cur = 0;
            dfs(0, -1);
            int sqn = SqrtDecomp.apprSqrt(n);
            SqrtDecomp.Query[] queries = new SqrtDecomp.Query[n];
            SqrtDecomp.Query[] originalQueries = new SqrtDecomp.Query[n];
            for (int i = 0; i < n; ++i) {
                queries[i] = new SqrtDecomp.Query(from[i], to[i], from[i] / sqn);
                originalQueries[i] = queries[i];
            }
            freqMap = new int[n + 1];
            Arrays.sort(queries, new SqrtDecomp.SortByBucket());
            freqSum = new long[n + 1];
            int l = 0, r = 0;
            add(color[flatten[0]]);

            for (SqrtDecomp.Query q : queries) {
                for (int i = r + 1; i <= q.r; ++i) {
                    add(color[flatten[i]]);
                }
                for (int i = q.l; i < l; ++i) {
                    add(color[flatten[i]]);
                }
                for (int i = l; i < q.l; ++i) {
                    remove(color[flatten[i]]);
                }
                for (int i = q.r + 1; i <= r; ++i) {
                    remove(color[flatten[i]]);
                }
                l = q.l;
                r = q.r;
                q.answer = freqSum[maxFreq];
            }

            for (SqrtDecomp.Query q : originalQueries) {
                out.print(q.answer + " ");
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 65536 / 2);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }

    static class SqrtDecomp {
        public static int apprSqrt(int n) {
            int ret = 0;
            while (ret * ret <= n) ++ret;
            return ret;
        }

        public static class Query {
            public int l;
            public int r;
            public int bucket;
            public long answer;

            public Query(int l, int r, int bucket) {
                this.l = l;
                this.r = r;
                this.bucket = bucket;
            }

        }

        public static class SortByBucket implements Comparator<SqrtDecomp.Query> {
            public int compare(SqrtDecomp.Query a, SqrtDecomp.Query b) {
                if (a.bucket != b.bucket)
                    return a.bucket - b.bucket;
                return a.r - b.r;
            }

        }

    }
}

