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.ByteArrayInputStream;
import java.io.IOException;
import java.util.*;

public class E {

    private static final int TEST_SZ = 100000;

    private final int n;
    private final Integer[] c;
    private final List<List<Integer>> links;

    private static class NodeProp {
        public Map<Integer, Integer> colorCount = new HashMap<>();
        public int max = 0;
        public long sum = 0;

        public void add(Integer color, Integer count) {
            Integer countNow = colorCount.get(color);
            if (countNow == null) {
                countNow = 0;
            }
            Integer newCount = countNow + count;
            colorCount.put(color, newCount);

            if (newCount > max) {
                sum = 0;
                max = newCount;
            }

            if (newCount == max) {
                sum += color;
            }
        }

        public void merge(NodeProp nodeProp) {
            for (Map.Entry<Integer, Integer> entry : nodeProp.colorCount.entrySet()) {
                add(entry.getKey(), entry.getValue());
            }
        }
    }

    private E(Scanner scanner) {
        n = scanner.nextInt();
        c = new Integer[n];
        for (int i = 0; i < n; i++) {
            c[i] = scanner.nextInt();
        }
        links = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            links.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            int a = scanner.nextInt() - 1;
            int b = scanner.nextInt() - 1;
            links.get(a).add(b);
            links.get(b).add(a);
        }
    }

    private void solve() {
        long[] result = new long[n];
        boolean[] visited = new boolean[n];
        visited[0] = true;
        dfs(0, result, visited);

        for (int i = 0; i < n; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }

    private NodeProp dfs(int source, long[] result, boolean[] visited) {
        NodeProp nodeProp = new NodeProp();

        for (Integer child : links.get(source)) {
            if (!visited[child]) {
                visited[child] = true;

                NodeProp childNodeProp = dfs(child, result, visited);

                // Small to large
                if (nodeProp.colorCount.size() < childNodeProp.colorCount.size()) {
                    NodeProp tmp = childNodeProp;
                    childNodeProp = nodeProp;
                    nodeProp = tmp;
                }

                nodeProp.merge(childNodeProp);
            }
        }

        nodeProp.add(c[source], 1);

        result[source] = nodeProp.sum;

        return nodeProp;
    }

    public static void main(String[] args) throws IOException {
//        beginTest();

        Scanner scanner = new Scanner(System.in);
        new E(scanner).solve();
        scanner.close();

//        endTest();
    }

    private static long time;

    private static void beginTest() throws IOException {
        StringBuilder sb = new StringBuilder();
        sb.append(String.valueOf(TEST_SZ));
        sb.append("\n");
        for (int i = 0; i < TEST_SZ; i++) {
            sb.append(String.valueOf(i + 1));
            sb.append(" ");
        }
        for (int i = 0; i < TEST_SZ - 1; i++) {
            sb.append("1 ");
            sb.append(i + 2);
            sb.append("\n");
        }

        System.setIn(new ByteArrayInputStream(sb.toString().getBytes()));

        time = System.currentTimeMillis();
    }

    private static void endTest() {
        System.out.println("Time: " + (System.currentTimeMillis() - time) + " ms");
    }
}
