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.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.HashMap;
import java.util.ArrayList;

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

    static class CF_600E {
        long[] ans;

        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] colors = new int[n];
            ans = new long[n];
            for (int i = 0; i < n; ++i) colors[i] = in.nextInt();
            Tree tree = new Tree(n, colors);

            for (int i = 0; i < n - 1; ++i) {
                int src = in.nextInt(), dest = in.nextInt();
                tree.addEdge(src - 1, dest - 1);
            }

            dfs(tree.root, new boolean[n]);

            for (long v : ans) {
                out.print(v + " ");
            }
        }

        Counter dfs(Node cur, boolean[] visited) {
            visited[cur.id] = true;
            Counter cnt = new Counter();
            cnt.add(cur.color, 1);
            for (Node c : cur.children.values()) {
                if (visited[c.id]) continue;
                Counter rs = dfs(c, visited);
                if (rs.f.size() > cnt.f.size())
                    cnt = rs.merge(cnt);
                else
                    cnt = cnt.merge(rs);
            }
            //System.out.printf("%d: %s\n", cur.id + 1, Arrays.toString(cnt.tops.toArray()));
            ans[cur.id] = cnt.sum;
            return cnt;
        }

        class Counter {
            Map<Integer, Integer> f = new HashMap<>();
            long max = 0;
            long sum = 0;
            List<Integer> tops = new ArrayList<>();

            void add(int key, int amt) {
                if (f.containsKey(key))
                    f.put(key, f.get(key) + amt);
                else
                    f.put(key, amt);
                int val = f.get(key);
                if (val == max) {
                    tops.add(key);
                    sum += key;
                }
                else if (val > max) {
                    max = val;
                    tops.clear();
                    tops.add(key);
                    sum = key;
                }
            }

            Counter merge(Counter other) {
                for (Map.Entry<Integer, Integer> e : other.f.entrySet()) {
                    add(e.getKey(), e.getValue());
                }
                return this;
            }

        }

        class Node {
            int id;
            int color;
            Map<Integer, Node> children = new HashMap<>();

            public Node(int id, int color) {
                this.id = id;
                this.color = color;
            }

        }

        class Tree {
            Node[] nodes;
            Node root;

            Tree(int n, int[] colors) {
                nodes = new Node[n];
                for (int i = 0; i < n; ++i)
                    nodes[i] = new Node(i, colors[i]);
                root = nodes[0];
            }

            void addEdge(int src, int dest) {
                nodes[src].children.put(dest, nodes[dest]);
                nodes[dest].children.put(src, nodes[src]);
            }

        }

    }
}
